-
逆波蘭式
鎖定
逆波蘭式算法定義
一個表達式E的後綴形式可以如下定義：
（1）如果E是一個變量或常量，則E的後綴式是E本身。
（2）如果E是E1 op E2形式的表達式，這裏op是任何二元操作符，則E的後綴式為E1'E2' op，這裏E1'和E2'分別為E1和E2的後綴式。
（3）如果E是（E1）形式的表達式，則E1的後綴式就是E的後綴式。
如：我們平時寫a+b，這是中綴表達式，寫成後綴表達式就是：ab+
(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為例子進行説明：
(a+b)*c的逆波蘭式為ab+c*，假設計算機把ab+c*按從左到右的順序壓入棧中，並且按照遇到運算符就把棧頂兩個元素出棧，執行運算，得到的結果再入棧的原則來進行處理，那麼ab+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
算法開始時，現將△如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 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>
#definemax100
usingnamespacestd;
char ex[max]; /*存儲後綴表達式*/
voidtrans()
{ /*將算術表達式轉化為後綴表達式*/
char str[max]; /*存儲原算術表達式*/
char stack[max]; /*作為棧使用*/
char ch;
int sum, 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");
return 0;
}數據結構版
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='a')||(ch='A')){c[j++]=ch;ch=e[i++];
//}
//c[j++]=' ';}
}
Pop(s1,ch);
while(ch!='@'){
c[j++]=ch;
Pop(s1,ch);
}
//c[j++]=;c[j++]=0;
return c;
}還有一種方法,用二叉樹。
