逆波蘭式（Reverse Polish notation，RPN，或逆波蘭記法），也叫後綴表達式（將運算符寫在運算元之後）
基本介紹
- 中文名：逆波蘭式
- 外文名：Reverse Polish notation，RPN
- 又稱：後綴表達式
- 使用方式：將運算符寫在運算元之後
定義,作用,算法實現,計算方法,舉例,算法圖示,程式實現,C/C++語言版,數據結構版,二叉樹法,
定義
一個表達式E的後綴形式可以如下定義：
（2）如果E是E1 op E2形式的表達式，這裡op是如何二元操作符，則E的後綴式為E1'E2' op，這裡E1'和E2'分別為E1和E2的後綴式。
（3)如果E是（E1）形式的表達式，則E1的後綴式就是E的後綴式。
(a+b)*c-(a+b)/e的後綴表達式為：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
作用
實現逆波蘭式的算法，難度並不大，但為什麼要將看似簡單的中序表達式轉換為複雜的逆波蘭式？原因就在於這個簡單是相對人類的思維結構來說的，對計算機而言中序表達式是非常複雜的結構。相對的，逆波蘭式在計算機看來卻是比較簡單易懂的結構。因為計算機普遍採用的記憶體結構是棧式結構，它執行先進後出的順序。
算法實現
首先需要分配2個棧，一個作為臨時存儲運算符的棧S1（含一個結束符號），一個作為輸入逆波蘭式的棧S2（空棧），S1棧可先放入優先權最低的運算符#，注意，中綴式應以此最低優先權的運算符結束。可指定其他字元，不一定非#不可。從中綴式的左端開始取字元，逐序進行如下步驟：
（1）若取出的字元是運算元，則分析出完整的運算數，該運算元直接送入S2棧
（2）若取出的字元是運算符，則將該運算符與S1棧棧頂元素比較，如果該運算符優先權(不包括括弧運算符)大於S1棧棧頂運算符優先權，則將該運算符進S1棧，否則，將S1棧的棧頂運算符彈出，送入S2棧中，直至S1棧棧頂運算符低於（不包括等於）該運算符優先權，最後將該運算符送入S1棧。
（3）若取出的字元是“（”，則直接送入S1棧頂。
（4）若取出的字元是“）”，則將距離S1棧棧頂最近的“（”之間的運算符，逐個出棧，依次送入S2棧，此時拋棄“（”。
（5）重複上面的1~4步，直至處理完所有的輸入字元
（6）若取出的字元是“#”，則將S1棧內所有運算符（不包括“#”），逐個出棧，依次送入S2棧。
完成以上步驟，S2棧便為逆波蘭式輸出結果。不過S2應做一下逆序處理。便可以按照逆波蘭式的計算方法計算了！
計算方法
新建一個表達式,如果當前字元為變數或者為數字，則壓棧，如果是運算符，則將棧頂兩個元素彈出作相應運算，結果再入棧，最後當表達式掃描完後，棧里的就是結果。
舉例
下面以(a+b)*c為例子進行說明：
1）a入棧（0位置）
2）b入棧（1位置）
3）遇到運算符“+”，將a和b出棧，執行a+b的操作，得到結果d=a+b，再將d入棧（0位置）
4）c入棧（1位置）
5）遇到運算符“*”，將d和c出棧，執行d*c的操作，得到結果e，再將e入棧（0位置）
經過以上運算，計算機就可以得到(a+b)*c的運算結果e了。
逆波蘭式除了可以實現上述類型的運算，它還可以派生出許多新的算法，數據結構，這就需要靈活運用了。逆波蘭式只是一種序列體現形式。
算法圖示
其中△代表一個標識，ω代表預算法，名字Q代表變數（如int a，b等），
算法用到三個棧：a棧，b棧，in棧。
其中a棧用來存儲逆波蘭式，b用來存儲△號和運算符，in棧為輸入棧。
第一豎排為b棧中符號，第一橫排為輸入棧中符號。
pop（in）為輸入棧棧頂元素出棧，pop（a，Q）為Q入a棧，NEXT算法即為進行下一輪循環，其中ω1<ω2為算符優先權，如“+”和“-”<“*”和“/”。pop（b，B），push（b，B）中B為臨時變數，用來存儲出棧的元素。stop為算法結束。
算法開始時，現將△如b棧，輸入棧以#號結尾。
?
輸入流 b[s-1] | 名字Q? | ( | ω2 | )? | # |
△ | POP(in); PUSH(a，Q) NEXT | POP(in); PUSH(b，△) NEXT | POP(in) PUSH(b，ω2) NEXT | POP(in) POP(b，B)?NEXT | STOP |
ω1 | POP(in) PUSH(a，Q)? NEXT | POP(in) PUSH(b，△) NEXT | 若ω1<ω2，則 POP(in) PUSH(b，ω2) NEXT? 若ω1≥ω2，則POP(in) POP(b，B）， PUSH(a,B) | POP(b，B) PUSH(a，B) | POP(b，B) PUSH(a，B) |
程式實現
C/C++語言版
//#include<iostream>#include<stdlib.h>#include<stdio.h>#include<stack>#include<math.h>#include<string.h>#definemax100usingnamespacestd;charex[max];/*存儲後綴表達式*/voidtrans(){/*將算術表達式轉化為後綴表達式*/charstr[max];/*存儲原算術表達式*/charstack[max];/*作為棧使用*/charch;intsum,i,j,t,top=0;printf("*****************************************\n");printf("*輸入一個求值的表達式，以#結束。*\n");printf("******************************************\n");printf("算數表達式：");i=0;/*獲取用戶輸入的表達式*/do{i++;//cin>>str[i];/*此步我用的是C++C語言的話在後面之所以用這個有一點區別都*/scanf("%c",&str[i]);}while(str[i]!='#'&&i!=max);sum=i;t=1;i=1;ch=str[i];i++;//while(ch!='#'){switch(ch){case'(':/*判定為左括弧*/top++;stack[top]=ch;break;case')':/*判定為右括弧*/while(stack[top]!='('){ex[t]=stack[top];top--;t++;}top--;break;case'+':/*判定為加減號*/case'-':while(top!=0&&stack[top]!='('){ex[t]=stack[top];top--;t++;}top++;stack[top]=ch;break;case'*':/*判定為乘除號*/case'/':while(stack[top]=='*'||stack[top]=='/'){ex[t]=stack[top];top--;t++;}top++;stack[top]=ch;break;case'':break;default:while(ch>='0'&&ch<='9'){/*判定為數字*/ex[t]=ch;t++;ch=str[i];i++;}i--;ex[t]='';t++;}ch=str[i];i++;}while(top!=0){ex[t]=stack[top];t++;top--;}ex[t]='';printf("\n\t原來表達式：");for(j=1;j<sum;j++)printf("%c",str[j]);printf("\n\t逆波蘭式：",ex);for(j=1;j<t;j++)printf("%c",ex[j]);}voidcompvalue(){/*計算後綴表達式的值*/floatstack[max],d;/*作為棧使用*/charch;intt=1,top=0;/*t為ex下標，top為stack下標*/ch=ex[t];t++;while(ch!=''){switch(ch){case'+':stack[top-1]=stack[top-1]+stack[top];top--;break;case'-':stack[top-1]=stack[top-1]-stack[top];top--;break;case'*':stack[top-1]=stack[top-1]*stack[top];top--;break;case'/':if(stack[top]!=0)stack[top-1]=stack[top-1]/stack[top];else{printf("\n\t除零錯誤!\n");exit(0);/*異常退出*/}top--;break;default:d=0;while(ch>='0'&&ch<='9'){d=10*d+ch-'0';/*將數字字元轉化為對應的數值*/ch=ex[t];t++;}top++;stack[top]=d;}ch=ex[t];t++;}printf("\n\t計算結果:%g\n",stack[top]);}intmain(){trans();compvalue();system("pause");return0;}數據結構版
int precede(char op)
{ int x;
switch(op)
{
case '*': x=2; break;
case '/': x=2; break;
case '+': x=1; break;
case '-': x=1; break;
default : x=0;
}
return x;
}
char *RPExpression(char *e)
{/* 返回表達式e的逆波蘭式 */
char *c;
c=(char*)malloc(sizeof(char)*20); //不能用char c[]
Stack s1;
InitStack(s1);
int i=0,j=0;
char ch;
Push(s1,'@');
ch=e[i++];
while(ch!= 0)
{
if(ch=='(')
{
Push(s1,ch);
ch=e[i++];
}
else if(ch==')')
{
while(Top(s1)!='(')
{
Pop(s1,c[j++]);
}
/* to[j++]=pop(&s1);*/
Pop(s1,ch);
ch=e[i++];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
char w;
w=Top(s1);
while(precede(w)>=precede(ch))
{
Pop(s1,c[j++]);
w=Top(s1);
}
Push(s1,ch);
ch=e[i++];
}
else
{
//while((ch<='z'&&ch>='a')||(ch<='Z' && ch>='A')){
c[j++]=ch;
ch=e[i++];
//}
//c[j++]=' ';
}
}
Pop(s1,ch);
while(ch!='@')
