C語言實現中綴表達式轉換為後綴表達式

本文實例為大家分享了C語言實現中綴表達式轉後綴表達式的具體代碼，供大家參考，具體內容如下

中綴表達式轉換為後綴表達式（思路）

1.創建棧

2.從左向右順序獲取中綴表達式

a.數字直接輸出

b.運算符



情況一：遇到左括號直接入棧，遇到右括號將棧中左括號之後入棧的運算符全部彈棧輸出，同時左括號出棧但是不輸出。

情況二：遇到乘號和除號直接入棧，直到遇到優先級比它更低的運算符，依次彈棧。

情況三：遇到加號和減號，如果此時棧空，則直接入棧，否則，將棧中優先級高的運算符依次彈棧（注意：加號和減號屬於同一個優先級，所以也依次彈棧）直到棧空或則遇到左括號為止，停止彈棧。（因為左括號要匹配右括號時才彈出）。

情況四：獲取完後，將棧中剩餘的運算符號依次彈棧輸出

例:比如將:2*(9+6/3-5)+4轉化為後綴表達式 2 9 6 3 / +5 - * 4 +

轉換算法代碼如下：

/*中綴轉後綴函數*/ void Change(SqStack *S,Elemtype str[]) { int i=0; Elemtype e; InitStack(S); while(str[i]!='�') { while(isdigit(str[i])) {/*過濾數字字符，直接輸出，直到下一位不是數字字符打印空格跳出循環 */ printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } /*加減運算符優先級最低，如果棧頂元素為空則直接入棧，否則將棧中存儲 的運算符全部彈棧，如果遇到左括號則停止，將彈出的左括號從新壓棧，因為左 括號要和又括號匹配時彈出，這個後面單獨討論。彈出後將優先級低的運算符壓入棧中*/ if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } /*當遇到右括號是，把括號裡剩餘的運算符彈出，直到匹配到左括號為止 左括號只彈出不打印（右括號也不壓棧）*/ else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } /*乘、除、左括號都是優先級高的，直接壓棧*/ else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='�') { break; } else { printf("

輸入格式錯誤！

"); return ; } i++; } /*最後把棧中剩餘的運算符依次彈棧打印*/ while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); } }





完整代碼如下：

#include

#include#include#include#define INITSIZE 20 #define INCREMENT 10 #define MAXBUFFER 20 #define LEN sizeof(Elemtype) /*棧的動態分配存儲結構*/ typedef char 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 c) { if(S->top - S->base >= S->StackSize) { S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT)); assert(S->base !=NULL); S->top =S->base+S->StackSize; S->StackSize+=INCREMENT; } *S->top++ = c; } /*求棧長*/ int StackLength(SqStack *S) { return (S->top - S->base); } /*彈棧操作*/ int PopStack(SqStack *S,Elemtype *c) { if(!StackLength(S)) { return 0; } *c=*--S->top; return 1; } /*中綴轉後綴函數*/ void Change(SqStack *S,Elemtype str[]) { int i=0; Elemtype e; InitStack(S); while(str[i]!='�') { while(isdigit(str[i])) {/*過濾數字字符，直接輸出，直到下一位不是數字字符打印空格跳出循環 */ printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } /*加減運算符優先級最低，如果棧頂元素為空則直接入棧，否則將棧中存儲 的運算符全部彈棧，如果遇到左括號則停止，將彈出的左括號從新壓棧，因為左 括號要和又括號匹配時彈出，這個後面單獨討論。彈出後將優先級低的運算符壓入棧中*/ if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } /*當遇到右括號是，把括號裡剩餘的運算符彈出，直到匹配到左括號為止 左括號只彈出不打印（右括號也不壓棧）*/ else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } /*乘、除、左括號都是優先級高的，直接壓棧*/ else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='�') { break; } else { printf("

輸入格式錯誤！

"); return ; } i++; } /*最後把棧中剩餘的運算符依次彈棧打印*/ while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); } } int main() { Elemtype str[MAXBUFFER]; SqStack S; gets(str); Change(&S,str); return 0; }

Tags: