前缀、中缀、后缀表达式
前缀(prefix)、中缀(infix)、后缀(suffix)表达式是对表达式的不同记法，其区别在于运算符相对于操作数的位置不同，前缀表达式的运算符位于操作数之前，中缀和后缀同理
举例：
中缀表达式：1 + (2 + 3) × 4 – 5
前缀表达式：- + 1 × + 2 3 4 5
后缀表达式：1 2 3 + 4 × + 5 –
中缀表达式
中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。
前缀表达式
前缀表达式的运算符位于两个相应操作数之前，前缀表达式又被称为前缀记法或波兰式
前缀表达式的计算机求值
- 从右至左扫描表达式
- 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈
- 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
示例：
计算前缀表达式的值：- + 1 × + 2 3 4 5
- 从右至左扫描，将5，4，3，2压入堆栈；
2）遇到+运算符，弹出2和3（2为栈顶元素，3为次顶元素），计算2+3的值，得到5，将5压入栈；
3）遇到×运算符，弹出5和4，计算5×4的值，得到20，将20压入栈；
4）遇到1，将1压入栈；
5）遇到+运算符，弹出1和20，计算1+20的值，得到21，将21压入栈；
6）遇到-运算符，弹出21和5，计算21-5的值，得到16为最终结果
可以看到，用计算机计算前缀表达式是非常容易的，不像计算后缀表达式需要使用正则匹配
后缀表达式
后缀表达式与前缀表达式类似，只是运算符位于两个相应操作数之后，后缀表达式也被称为后缀记法或逆波兰式
后缀表达式的计算机求值
与前缀表达式类似，只是顺序是从左至右：
- 从左至右扫描表达式
- 遇到数字时，将数字压入栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素op 栈顶元素），并将结果入栈
- 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
示例：
计算
计算后缀表达式的值：1 2 3 + 4 × + 5 –
1）从左至右扫描，将1，2，3压入栈；
2）遇到+运算符，3和2弹出，计算2+3的值，得到5，将5压入栈；
3）遇到4，将4压入栈
4）遇到×运算符，弹出4和5，计算5×4的值，得到20，将20压入栈；
5）遇到+运算符，弹出20和1，计算1+20的值，得到21，将21压入栈；
6）遇到5，将5压入栈；
7）遇到-运算符，弹出5和21，计算21-5的值，得到16为最终结果
中缀转为前缀、后缀表达式
转化步骤：
- 按照运算符的优先级对所有的运算单位加括号
- 将运算符移动到对应括号的前面（前缀表达式）或后面（后缀表达式）
- 去掉括号，得到前缀或后缀表达式
示例：
中缀表达式：1+(2+3)×4-5
1）加括号
式子变成 ((1+((2+3)×4))-5)
2）移动运算符
对于前缀表达式，变成了 -(+(1×(+(23)4))5)
对于后缀表达式：变成了((1((23)+4)×)+5)-
3）去掉括号
前缀表达式： – + 1 × + 2 3 4 5
后缀表达式：1 2 3 + 4 × + 5 –
小结
- 前缀、中缀、后缀是根据运算符与操作数的相对位置来划分的
- 中缀表达式符合人的计算习惯，而前缀和后缀表达式适合计算机计算
- 前缀表达式和后缀表达式计算的时候都是从一个方向扫描表达式，遇到数字压入栈，遇到运算符弹出栈顶的两个数进行运算并将结果入栈，重复直到结束
- 前缀和后缀表达式已经内在地包含运算顺序，因此不用括号来确定优先级
代码示例
后缀表达式
#include <bits/stdc++.h>
using namespace std;
map<char, int> op{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
int main(){
string str, newstr;
stack<char> st;
cin >> str;
for(int i = 0; i<str.size(); i++){
if(str[i] == '('){
st.push(str[i]);
} else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/'){
while(!st.empty() && op[st.top()] >= op[str[i]]){ // 栈不为空，且栈顶优先级大于当前op
newstr += st.top() + string(" ");
st.pop();
}
st.push(str[i]);
} else if(isdigit(str[i])){
string t(1, str[i]);
while(i+1 < str.size() && isdigit(str[i+1])){
t += str[i+1];
i++;
}
newstr += t + string(" ");
} else if(str[i] == ')'){
while(st.top() != '('){
newstr += st.top() + string(" ");
st.pop();
}
st.pop();
}
}
while(!st.empty()){
newstr += st.top() + string(" ");
st.pop();
}
cout << newstr << endl; //输出后缀表达式
//通过后缀表达式计算结果
stack<int> calu;
for(int i = 0; i<newstr.size(); i++){
if(newstr[i] == ' ')
continue;
if(isdigit(newstr[i])){
int t = newstr[i] - '0';
while(i+1 < newstr.size() && isdigit(newstr[i+1])){
t = t * 10 + newstr[i+1] - '0';
i++;
}
calu.push(t);
} else {
int t = calu.top(); calu.pop();
if(newstr[i] == '*')
t = calu.top() * t, calu.pop();
else if(newstr[i] == '/')
t = calu.top() / t, calu.pop();
else if(newstr[i] == '+')
t = calu.top() + t, calu.pop();
else if(newstr[i] == '-')
t = calu.top() - t, calu.pop();
calu.push(t);
}
}
cout << calu.top() << endl;
return 0;
}
y总写法
两种写法相同，只不过第二种写法省略了转换为后缀表达式的中间步骤
#include <bits/stdc++.h>
using namespace std;
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
stack<int> num;
stack<char> op;
int eval(){
int a = num.top(); num.pop();
int b = num.top(); num.pop();
char c = op.top(); op.pop();
int x;
if(c == '*')
x = a * b;
else if(c == '/')
x = b / a;
else if(c == '+')
x = a + b;
else if(c == '-')
x = b - a;
num.push(x);
}
int main(){
string str;
cin >> str;
for(int i = 0; i<str.size(); i++){
auto c = str[i];
if(c == '(')
op.push(c);
else if(isdigit(c)){
int x = c - '0';
while(i+1 < str.size() && isdigit(str[i+1]))
x = x * 10 + str[++i] - '0';
num.push(x);
} else if(c == ')'){
while(op.top() != '(')
eval();
op.pop();
} else {
while(op.size() && pr[op.top()] >= pr[c])
eval();
op.push(c);
}
}
while(op.size()) eval();
cout << num.top() << endl;
return 0;
}
