前缀、中缀与后缀表达式
计算机中一般使用三种表达式，分别是中缀表达式(Infix)、前缀表达式(Prefix)、后缀表达式(Postfix)。
下表列出了它们的基本表示形式：
| 类型 |
Infix |
Prefix |
Postfix |
| 形式 |
<operand><operator><operand> |
<operator><operand><operand> |
<operand><operand><operator> |
| 例子 |
a+b*c |
+a*bc |
abc*+ |
后缀表达式的计算方法
为什么要将表意清晰的中缀表达式转换成形式比较特殊的后缀表达式呢？这是因为中缀表达式的运算需要人为地遵循一些运算法则，而后缀表达式只需要遵循一个固定的运算法则即可完成运算。
后缀表达式的计算方法为：
从左到右对后缀表达式进行扫描，当遇到运算符时，将运算符与它前面两个数字组合成一个算式进行计算，用结果取代两个数字以及运算符的位置，继续向后扫描，直到表达式变成一个值，该值即为表达式的值。
我们发现，这与栈的工作模式非常类似，于是，可以写出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int EvaluatePostfix(int exp[]){
stack<int> S;
for(int i = 0 ; i <= strlen(exp)-1 ; i++){
if(exp[i] is operand)
S.push(exp[i]);
else if(exp[i] is operator){
int op1 = S.top();
S.pop();
int op2 = S.top();
S.pop();
res = Perform(exp[i],op1,op2);
S.push(res);
}
}
return S.top();
}
|
将中缀表达式转换为后缀表达式
那么如何将Infix转换为Postfix，从而可以被程序计算呢？
对比两种表达式
Infix: A + B * C
Postfix:A B C * +
我们发现操作数之间的相对位置并无改变，只是操作符的位置发生变化。下面提供一个转换的方法，依然使用栈来实现。
| Infix |
A + B * C - D * E |
| Postfix |
A |
| Stack |
|
| Infix |
A + B * C - D * E |
| Postfix |
AB |
| Stack |
+ |
- 现在我们遇到了第二个符号，如果此时栈顶符号的运算级别大于等于该符号，那么就将栈顶的符号弹出并且加入Postfix，直到不符合该条件或者栈为空时，将该符号（也就是遍历到的符号）入栈。
| Infix |
A + B * C - D * E |
| Postfix |
AB |
| Stack |
+ * |
- 直到遍历结束，将栈中剩余符号依次全部弹出并加入Postfix。
| Infix |
A + B * C - D * E |
| Postfix |
A B C * + D E * - |
| Stack |
|
但是我们并没有考虑Infix带括号的情况。如果表达式带括号的话，解决方案如下：
遇到左括号让左括号入栈，如果栈顶是左括号，遇到操作符直接入栈
直到遇到右括号，将栈顶的元素弹出并加入Postfix直到遇到对应的左括号时停止
综合以上方法可以写出对应代码
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
| void InfixtoPostfix(char exp[],char res[]){
stack<char> S;
int j=0;
for(int i=0;i<=strlen(exp)-1;i++){
if(exp[i] is operand)
res[j++] = exp[i];
else if(exp[i] is operator){
while(!S.empty()&&HasHigherPrec(S.top,exp[i])&&!IsOpeningParentheses(S.top())){
res[j++] = S.top();
S.pop();
}
S.push(exp[i]);
}
else if(exp[i] == '(')
S.push(exp[i]);
else if(exp[i] == ')'){
while(!S.empty()&&!IsOpeningParentheses(S.top())){
res[j++] = S.top();
S.pop();
}
S.pop();
}
}
while(!S.empty()){
res[j++] = S.top();
S.pop();
}
}
|
编写10以内的混合运算计算器
任务
输入包括10以内的数字和+、-、*、(、)运算符的合法表达式，输出它的Infix、Postfix以及运算结果。
代码
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
| #include<iostream>
#include<stack>
using namespace std;
bool Isoperator(char c){
if(c == '+'||c == '-'||c == '*')
return true;
else
return false;
}
bool HasHigherPrec(char a,char b){
if(b == '+'||b == '-')
return true;
else{
if(a == '*') return true;
else return false;
}
}
bool IsopeningPar(char c){
if(c == '(') return true;
else return false;
}
void InfixtoPostfix(char exp[],char res[]){
int j=0;
stack<char> S;
for(int i = 0; i <= strlen(exp)-1 ;i++){
if(exp[i]>=48&&exp[i]<=57){
res[j++] = exp[i];
}
else if(Isoperator(exp[i])){
while(!S.empty()&&HasHigherPrec(S.top(),exp[i])&&!IsopeningPar(S.top())){
res[j++] = S.top();
S.pop();
}
S.push(exp[i]);
}
else if(exp[i]=='(')
S.push(exp[i]);
else if(exp[i]==')'){
while(!S.empty()&&!IsopeningPar(S.top())){
res[j++] = S.top();
S.pop();
}
S.pop();
}
}
while(!S.empty()){
res[j++] = S.top();
S.pop();
}
}
int Perform(char c,int a,int b){
if(c == '+')
return b+a;
if(c == '-')
return b-a;
if(c == '*')
return b*a;
}
int EvaluatePostfix(char res[]){
stack<int> A;
int op1,op2,op;
for(int i=0;i<=strlen(res)-1;i++){
if(!Isoperator(res[i]))
A.push((int)(res[i]-'0'));
else if(Isoperator(res[i])){
op1 = A.top();
A.pop();
op2 = A.top();
A.pop();
op = Perform(res[i],op1,op2);
A.push(op);
}
}
return A.top();
}
int main(){
char exp[100];
char res[100];
gets(exp);
printf("Infix: %s\n",exp);
InfixtoPostfix(exp,res);
printf("Postfix: %s\n",res);
printf("The result is %d",EvaluatePostfix(res));
return 0;
}
|
输入/出结果
1
2
3
4
| ((1+2)*3-4)*5+(6-7)
Infix: ((1+2)*3-4)*5+(6-7)
Postfix: 12+3*4-5*67-+
The result is 24
|