定義
一個表達式E的後綴形式可以如下定義：
（1）如果E是一個變量或常量，則E的後綴式是E本身。
（2）如果E是E1opE2形式的表達式，這裡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/-
作用
實現逆波蘭式的算法，難度并不大，但為什麼要将看似簡單的中序表達式轉換為複雜的逆波蘭式？原因就在于這個簡單是相對人類的思維結構來說的，對計算機而言中序表達式是非常複雜的結構。相對的，逆波蘭式在計算機看來卻是比較簡單易懂的結構。因為計算機普遍采用的内存結構是棧式結構，它執行先進後出的順序。逆波蘭算法(RPN)在不使用括号的情況下即能完成表達式的表達和求值。
算法實現
将一個普通的中序表達式轉換為逆波蘭表達式的一般算法是：
首先需要分配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++語言版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
//#include
#include
#include
#include
#include
#include
#definemax100
usingnamespacestd;
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("nt原來表達式：");
for (j = 1; j < sum; j++)
printf("%c", str[j]);
printf("nt逆波蘭式：", 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("nt除零錯誤!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("nt計算結果:%gn", 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 cStack 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;
}
二叉樹法
将最終進行的運算符記為根節點，将兩邊的表達式分别記為左右子樹，依次進行直到所有的運算符與數字或字母标在一棵二叉樹上。然後對二叉樹進行後序遍曆即可。
相關詞條
相關搜索
其它詞條
