本文實例為大家分享了C++實現中綴表達式轉後綴表達式的具體代碼，供大家參考，具體內容如下
題目：現有中綴表達式如：1+(2-3)*4+10/5
請用棧的特性編寫一個程序，使得程序輸出後綴表達式
分析如下：
STEP1：
1+(2-3)*4+10/5
首先遇到第一個輸入是數字1，數字在後綴表達式中都是直接輸出，接著是符號“+”，入棧：
STEP2：
1+(2-3)*4+10/5
第三個字符是“(”，依然是符號，入棧，接著是數字2，輸出，然後是符號“-”，入棧：
STEP3：
1+(2-3)*4+10/5
接下來是數字3，輸出，緊跟著是“)”，此時，我們需要去匹配棧裡的“(”，然後再匹配前將棧頂數據依次出棧（這就好比括號裡優先執行的道理）：
STEP4：
1+(2-3)*4+10/5
緊接著是符號“*”，直接入棧
STEP5：
1+(2-3)*4+10/5
遇到數字4，輸出，之後是符號“+”，此時棧頂元素是符號“*”，按照先乘除後加減原理，此時棧頂的乘號優先級比即將入棧的加好要大，所以出棧。
棧中第二個元素是加號，按理來說大家平起平坐，但是按照先來後到的原則，棧裡的加號呆得太久了，也要出棧透透氣。（同理如果棧裡還有其他操作符，也是出棧）
最後把剛剛的那個加號入棧，操作如下圖：
STEP6：
1+(2-3)*4+10/5
緊接著數字10，輸出，最後是符號“/”，進棧：
STEP7：
1+(2-3)*4+10/5
最後一個數字5，輸出，所有的輸入處理完畢，但是棧中仍然有數據，所以將棧中符號依次出棧。
總結規則：
從左到右遍歷中綴表達式的每個數字和符號，若是數字則直接輸出，若是符號，則判斷其與棧頂符號的優先級，是右括號或者優先級低於棧頂符號，則棧頂元素依次出棧並輸出，直到遇到左括號或棧空才將低優先級的那個符號入棧
代碼實現如下：
#include
#include#define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 typedef char ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; InitStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE; } Push(sqStack *s, ElemType e) { // 棧滿，追加空間，魚油必須懂！ if( s->top - s->base >= s->stackSize ) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base + s->stackSize; s->stackSize = s->stackSize + STACKINCREMENT; } *(s->top) = e; // 存放數據 s->top++; } Pop(sqStack *s, ElemType *e) { if( s->top == s->base ) return; *e = *--(s->top); // 將棧頂元素彈出並修改棧頂指針 } int StackLen(sqStack s) { return (s.top - s.base); } int main() { sqStack s; char c, e; InitStack( &s ); printf("請輸入中綴表達式，以#作為結束標誌："); scanf("%c", &c); while( c != '#' ) { while( c>='0' && c<='9' ) { printf("%c", c); scanf("%c", &c); if( c<'0' c="">'9' ) { printf(" "); } } if( ')' == c ) { Pop(&s, &e); while( '(' != e ) { printf("%c ", e); Pop(&s, &e); } } else if( '+'==c || '-'==c ) { if( !StackLen(s) ) { Push(&s, c); } else { do { Pop(&s, &e); if( '(' == e ) { Push(&s, e); } else { printf("%c ", e); } }while( StackLen(s) && '('!=e ); Push(&s, c); } } else if( '*'==c || '/'==c || '('==c ) { Push(&s, c); } else if( '#'== c ) { break; } else { printf("
出錯：輸入格式錯誤！
"); return -1; } scanf("%c", &c); } while( StackLen(s) ) { Pop(&s, &e); printf("%c ", e); } return 0; }
