歡迎您光臨本站 註冊首頁

C語言利用棧實現對後綴表達式的求解

←手機掃碼閱讀     火星人 @ 2020-04-27 , reply:0


逆波蘭表達式:

逆波蘭表達式又叫後綴表達式。它是由相應的語法樹的後序遍歷的結果得到的。

例:5 - 8*(6 + 7) + 9 / 4:



其中綴表達式為:5 - 8 * 6 + 7 + 9 / 4

其語法樹如下:

因此根據語法樹可以得出他後序遍歷(後綴表達式)為:

5 8 6 7 + * - 9 4 / +

這樣就實現了中綴表達式到後綴表達式的轉換。

同樣的也可以得出他的前序遍歷(前綴表達式也稱波蘭表達式):

+ - 5 * 8 + 6 7 / 9 4

逆波蘭表達式計算實現原理:

1.首先當遇到運算操作數時將其進行push操作;

2.當遇到操作符是將此時的棧pop兩次,先取出的棧頂為右操作數;

3.執行此方法到整個數組遍歷完。

實現算法如下:

void CalFunction(SqStack *S,char str[]) {/*實現浮點型數據後綴表達式的加減乘除*/ Elemtype number,e,d; char arr[MAXBUFFER]; int i=0,j=0; InitStack(S); while(str[i]!='�') { while(isdigit(str[i])||str[i]=='.') //過濾數字 { arr[j++]=str[i++]; arr[j]='�'; if( j >= MAXBUFFER ) { printf("輸入單個數據過大!

"); return ; } if(str[i]==' ') { number=atof(arr); //利用atof函數將數字字符串轉化為double型數據 PushStack(S,number); //將轉換的數進行壓棧 j=0; //這裡不要忘記將j重新初始化進行下個數據的轉化 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("輸入出錯,分母為零!

"); return ; } PushStack(S,d/e); break; } i++; //繼續遍歷直到遍歷字符串結束 } PopStack(S,&e); printf("計算結果為:%lf",e); }

完整代碼如下:

#include

#include#include#include#define INITSIZE 20 #define INCREMENT 10 #define MAXBUFFER 10 #define LEN sizeof(Elemtype) /*棧的動態分配順序存儲結構*/ 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]!='�') { while(isdigit(str[i])||str[i]=='.') //過濾數字 { arr[j++]=str[i++]; arr[j]='�'; if( j >= MAXBUFFER ) { printf("輸入單個數據過大!

"); return ; } if(str[i]==' ') { number=atof(arr); //利用atof函數將數字字符轉化為double型數據 PushStack(S,number); //將轉換的數進行壓棧 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("輸入出錯,分母為零!

"); return ; } PushStack(S,d/e); break; } i++; } PopStack(S,&e); printf("計算結果為:%lf",e); } int main() { char str[100]; SqStack S; printf("請按逆波蘭表達式輸入數據,每個數據之間用空格隔開:"); gets(str); CalFunction(&S,str); return 0; } // 檢測用例 5 - (6 + 7) * 8 + 9 / 4 // 輸入:5 8 6 7 + * - 9 4 / + # // 輸出: - 96.750000

[火星人 ] C語言利用棧實現對後綴表達式的求解已經有122次圍觀

http://coctec.com/docs/c/language/show-post-231854.html