歡迎您光臨本站 註冊首頁

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

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

本文實例為大家分享了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; }

[火星人 ] C語言實現中綴表達式轉換為後綴表達式已經有119次圍觀

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