C語(yǔ)言利用棧實(shí)現(xiàn)對(duì)后綴表達(dá)式的求解

更新時(shí)間：2020年04月26日 17:17:07 作者：蒼之羽

這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言利用棧實(shí)現(xiàn)對(duì)后綴表達(dá)式的求解，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了C語(yǔ)言實(shí)現(xiàn)對(duì)后綴表達(dá)式（逆波蘭表達(dá)式）的求解代碼，供大家參考，具體內(nèi)容如下

逆波蘭表達(dá)式：

逆波蘭表達(dá)式又叫后綴表達(dá)式。它是由相應(yīng)的語(yǔ)法樹(shù)的后序遍歷的結(jié)果得到的。
例：5 - 8*(6 + 7) + 9 / 4：

其中綴表達(dá)式為：5 - 8 * 6 + 7 + 9 / 4

其語(yǔ)法樹(shù)如下：

因此根據(jù)語(yǔ)法樹(shù)可以得出他后序遍歷（后綴表達(dá)式）為：
5 8 6 7 + * - 9 4 / +

這樣就實(shí)現(xiàn)了中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換。
同樣的也可以得出他的前序遍歷（前綴表達(dá)式也稱(chēng)波蘭表達(dá)式）：
　+ - 5 * 8 + 6 7 / 9 4

逆波蘭表達(dá)式計(jì)算實(shí)現(xiàn)原理：
1.首先當(dāng)遇到運(yùn)算操作數(shù)時(shí)將其進(jìn)行push操作；

2.當(dāng)遇到操作符是將此時(shí)的棧pop兩次，先取出的棧頂為右操作數(shù)；

3.執(zhí)行此方法到整個(gè)數(shù)組遍歷完。

實(shí)現(xiàn)算法如下：

void CalFunction(SqStack *S,char str[])
{/*實(shí)現(xiàn)浮點(diǎn)型數(shù)據(jù)后綴表達(dá)式的加減乘除*/
 Elemtype number,e,d;
 char arr[MAXBUFFER];
 int i=0,j=0;
 
 InitStack(S);
 
 while(str[i]!='\0')
 {
 while(isdigit(str[i])||str[i]=='.') //過(guò)濾數(shù)字
 {
 arr[j++]=str[i++];
 arr[j]='\0';
 
 if( j >= MAXBUFFER )
 {
 printf("輸入單個(gè)數(shù)據(jù)過(guò)大！\n");
 return ;
 }
 if(str[i]==' ')
 {
 number=atof(arr); //利用atof函數(shù)將數(shù)字字符串轉(zhuǎn)化為double型數(shù)據(jù)
 PushStack(S,number); //將轉(zhuǎn)換的數(shù)進(jìn)行壓棧
 j=0;   //這里不要忘記將j重新初始化進(jìn)行下個(gè)數(shù)據(jù)的轉(zhuǎn)化
 break;
 }
 }
 /*如果遇到操作運(yùn)算符則，彈出兩個(gè)數(shù)據(jù)進(jìn)行運(yùn)算，然后將得出的結(jié)果重新入棧*/
 switch(str[i])
 {
 case '+':
 PopStack(S,&e);
 PopStack(S,&d);
 PushStack(S,d+e);
 break;
 case '-':
 PopStack(S,&e);
 PopStack(S,&d);
 PushStack(S,d-e);
 break;
 case '*':
 PopStack(S,&e);
 PopStack(S,&d);
 PushStack(S,d*e);
 break;
 case '/':
 PopStack(S,&e);
 PopStack(S,&d);
 if(e == 0)
 {
 printf("輸入出錯(cuò)，分母為零！\n");
 return ;
 }
 PushStack(S,d/e);
 break;
 }
 i++; //繼續(xù)遍歷直到遍歷字符串結(jié)束
 }
 
 PopStack(S,&e);
 printf("計(jì)算結(jié)果為：%lf",e); 
}

完整代碼如下：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<ctype.h>

#define INITSIZE 20
#define INCREMENT 10
#define MAXBUFFER 10
#define LEN sizeof(Elemtype)

/*棧的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)*/
typedef double Elemtype;
typedef struct{
 Elemtype *base;
 Elemtype *top;
 int StackSize; 
}SqStack;

void InitStack(SqStack *S)
{
 S->base=(Elemtype*)malloc(LEN*INITSIZE);
 assert(S->base != NULL);
 S->top=S->base;
 S->StackSize=INITSIZE;
}

void PushStack(SqStack *S,Elemtype e)
{
 if(S->top - S->base >= S->StackSize)
 {
 S->base=(Elemtype*)realloc(S->base,(S->StackSize+INCREMENT)*LEN);
 assert(S->base !=NULL);
 S->top=S->base+S->StackSize;
 S->StackSize+=INCREMENT;
 }
 *S->top =e;
 S->top++;
}

void PopStack(SqStack *S,Elemtype *e)
{
 *e=*--S->top;
}

void CalFunction(SqStack *S,char str[])
{
 Elemtype number,e,d;
 char arr[MAXBUFFER];
 int i=0,j=0;
 
 InitStack(S);
 
 while(str[i]!='\0')
 {
 while(isdigit(str[i])||str[i]=='.') //過(guò)濾數(shù)字
 {
 arr[j++]=str[i++];
 arr[j]='\0';
 
 if( j >= MAXBUFFER )
 {
 printf("輸入單個(gè)數(shù)據(jù)過(guò)大！\n");
 return ;
 }
 if(str[i]==' ')
 {
 number=atof(arr); //利用atof函數(shù)將數(shù)字字符轉(zhuǎn)化為double型數(shù)據(jù)
 PushStack(S,number); //將轉(zhuǎn)換的數(shù)進(jìn)行壓棧
 j=0;
 break;
 }
 }
 
 switch(str[i])
 {
 case '+':
 PopStack(S,&e);
 PopStack(S,&d);
 PushStack(S,d+e);
 break;
 case '-':
 PopStack(S,&e);
 PopStack(S,&d);
 PushStack(S,d-e);
 break;
 case '*':
 PopStack(S,&e);
 PopStack(S,&d);
 PushStack(S,d*e);
 break;
 case '/':
 PopStack(S,&e);
 PopStack(S,&d);
 if(e == 0)
 {
 printf("輸入出錯(cuò)，分母為零！\n");
 return ;
 }
 PushStack(S,d/e);
 break;
 }
 i++; 
 }
 
 PopStack(S,&e);
 printf("計(jì)算結(jié)果為：%lf",e); 
}

int main()
{
 char str[100];
 SqStack S;
 printf("請(qǐng)按逆波蘭表達(dá)式輸入數(shù)據(jù),每個(gè)數(shù)據(jù)之間用空格隔開(kāi):");
 gets(str);
 CalFunction(&S,str);
 return 0;
}


// 檢測(cè)用例 5 - (6 + 7) * 8 + 9 / 4

// 輸入：5 8 6 7 + * - 9 4 / + # 

// 輸出： - 96.750000

運(yùn)行效果截圖如下：