本文最后编辑于 前，其中的内容可能需要更新。
一、简介
前缀表达式、中缀表达式、后缀表达式都是数学中四则运算的表达方式。
日常生活中我们最常见的形如(a+b)xc表达式即中缀表达式，即操作符位于左右操作数的中间。但是计算机中利用中缀表达式计算求值则比较麻烦，需要将中缀表达式转换成表达式树，然后再递归进行计算，时间和空间复杂度都比较高。
为了便于计算机运算，波兰数学家Jan Lukasiewicz发明了前缀表达式，将操作符写在操作数的前面(如x+abc)，这样可以将四则运算用到的结构由树变成线性结构，大大提升了运算效率。为了纪念，人们将前缀称为波兰式。
但是因为将中缀表达式转变为前缀表达式，以及前缀表达式求值，都需要从右往左（从后往前）扫描表达式，不符合日常习惯，所以基于和前缀表达式类似的逻辑，又产生了后缀表达式，又称为逆波兰式。
计算机中通常采用的都是后缀表达式。
二、中缀表达式转换后缀表达式
- 利用栈存放操作符，记栈为S1；
- 从左往右扫描中缀表达式，当读到一个操作数时，立即将其输出；
- 当读到一个操作符
+-x()时：
- 如果是
(时，直接入栈S1；
- 如果是
+-x，则比较该操作符与栈顶优先级，如果该操作符比栈顶优先级高或者栈顶是(，则直接入栈S1；否则弹出栈顶元素到输出，然后继续比较；其中优先级：( > x > + = -。
- 如果是
)，则将栈S1元素弹出到输出，直到遇到一个(为止；此时将(移除栈S1但不输出；
- 当扫描完成，将栈S1中的元素挨个弹出到输出中。
例将中缀式1+((2+3)×4)-5转为后缀式：
| 扫描元素 |
栈S1 |
输出 |
说明 |
| 1 |
空 |
1 |
数字直接输出 |
| + |
+ |
1 |
栈空，+直接入栈 |
| ( |
+( |
1 |
(直接入栈 |
| ( |
+(( |
1 |
(直接入栈 |
| 2 |
+(( |
1 2 |
数字直接输出 |
| + |
+((+ |
1 2 |
栈顶是(，+直接入栈 |
| 3 |
+((+ |
1 2 3 |
数字直接输出 |
| ) |
+( |
1 2 3 + |
)，弹出栈中元素直到遇到( |
| x |
+(x |
1 2 3 + |
栈顶是(，x直接入栈 |
| 4 |
+(x |
1 2 3 + 4 |
数字直接输出 |
| ) |
+ |
1 2 3 + 4 x |
)，弹出栈中元素直到遇到( |
| - |
- |
1 2 3 + 4 x + |
+-优先级相同，所以弹出+，压入- |
| 5 |
- |
1 2 3 + 4 x + 5 |
数字直接输出 |
| 完成 |
空 |
1 2 3 + 4 x + 5 - |
将栈中元素挨个弹出到输出 |
三、后缀表达式求值
- 利用栈存放操作数和中间结果，记栈为S1；
- 从左往右扫描后缀表达式，当读到一个操作数时，将其压入栈S1中；
- 当读到一个操作符时，从栈中弹出两个操作数，并用该操作符进行计算，再将所得结果压入栈中；
- 当扫描完成，栈中剩下唯一一个元素就是计算结果。
以后缀式1 2 3 + 4 x + 5 -为例：
| 扫描元素 |
栈S1 |
说明 |
| 1 |
1 |
数字直接入栈 |
| 2 |
1 2 |
数字直接入栈 |
| 3 |
1 2 3 |
数字直接入栈 |
| + |
1 5 |
弹出2 3，并将2+3结果入栈 |
| 4 |
1 5 4 |
数字直接入栈 |
| x |
1 20 |
弹出 5 4，并将5x4结果入栈 |
| + |
21 |
弹出1 20，并将1+20结果入栈 |
| 5 |
21 5 |
数字直接入栈 |
| - |
16 |
弹出21 5，并将21-5结果入栈 |
| 完成 |
16 |
栈中最后元素即为表达式结果 |
示例代码：
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
| #include <string>
#include <vector>
#include <stack>
using namespace std;
inline bool isdigit(char c) {
return c- '0' >= 0 && c - '0' <= 9;
}
inline bool isOperator(const string& str) {
return str.size() == 1 && !isdigit(str[0]);
}
vector<string> parseInfixExpression(const string& exp) {
vector<string> tokens;
for(size_t i(0); i < exp.size(); ++i) {
char c = exp[i];
if(c == ' ') {
continue;
}
switch(c) {
case '+':
case '*':
case '/':
case '(':
case ')': {
tokens.push_back("" + c);
break;
}
case '-': {
if(i > 0 && (exp[i-1] == ')' || isdigit(exp[i-1]))) {
tokens.push_back("" + c);
} else {
tokens.push_back("#");
}
break;
}
default: {
string temp = "" + c;
while(i+1 < exp.size() && isdigit(exp[i+1])) {
temp += exp[++i];
}
tokens.push_back(temp);
break;
}
}
}
return tokens;
}
int getPriority(const string& op) {
int priority = 0;
if(op=="#")
priority = 3;
else if(op=="*"||op=="/")
priority = 2;
else if(op=="+"||op=="-")
priority = 1;
else if(op=="(")
priority = 0;
return priority;
}
vector<string> infixToPostfix(const vector<string> infixTokens) {
vector<string> postfixTokens;
stack<string> opStack;
for(size_t i(0); i < infixTokens.size(); ++i) {
const string& t = infixTokens[i];
if(!isOperator(t)) {
postfixTokens.push_back(t);
} else if (t == "(") {
opStack.push(t);
} else if (t == "#" || t == "+" || t == "-" || t == "*" || t == "/") {
int priToken = getPriority(t);
while(!opStack.empty()) {
int priTop = getPriority(opStack.top());
if(priToken <= priTop) {
postfixTokens.push_back(opStack.top());
opStack.pop();
} else {
break;
}
}
opStack.push(t);
} else if (t == ")") {
while(!opStack.empty()) {
if(opStack.top() == "(") {
opStack.pop();
break;
}
postfixTokens.push_back(opStack.top());
opStack.pop();
}
}
}
while(!opStack.empty()) {
postfixTokens.push_back(opStack.top());
opStack.pop();
}
return postfixTokens;
}
int calcPostfix(const vector<string>& tokens) {
stack<int> resStack;
for(size_t i(0); i < tokens.size(); ++i) {
const string& t = tokens[i];
if(!isOperator(t)) {
resStack.push(atoi(t.c_str()));
} else if (t == "#") {
int temp = resStack.top();
resStack.pop();
resStack.push(0 - temp);
} else if (t == "+") {
int r = resStack.top();
resStack.pop();
int l = resStack.top();
resStack.pop();
resStack.push(l + r);
} else if (t == "-") {
int r = resStack.top();
resStack.pop();
int l = resStack.top();
resStack.pop();
resStack.push(l - r);
} else if (t == "*") {
int r = resStack.top();
resStack.pop();
int l = resStack.top();
resStack.pop();
resStack.push(l * r);
} else if (t == "/") {
int r = resStack.top();
resStack.pop();
int l = resStack.top();
resStack.pop();
resStack.push(l / r);
}
}
return resStack.top();
}
|