我们平时写的算式,比如 3 + 4 * 2,运算符夹在数字中间,这叫中缀表达式。计算机处理它其实很麻烦,因为要考虑优先级和括号。把运算符挪到数字前面或后面,处理起来就简单多了。
这一章讲三种表达式的转换与求值,是 CSP 第一轮单项选择题的常见考点(2022、2023 年入门级都出现过),也是栈的经典应用。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| CSP-J/S 入门级 | 3.1 线性结构中的栈,用于表达式求值 | 后缀表达式的求值、中缀转后缀 |
| NOI 入门级 | 1.3.1 栈;1.4.1 算法描述 | 全章 |
| CSP-J/S 第一轮 | 前缀、中缀、后缀表达式的转换与求值 | 全章 |
三种表达式
同一个算式 3 + 4 * 2 的三种写法:
| 名称 | 特点 | 例子 |
|---|---|---|
| 中缀表达式 | 运算符在操作数中间,人习惯的写法 | 3 + 4 * 2 |
| 前缀表达式 | 运算符在操作数前面,也叫波兰表达式 | + 3 * 4 2 |
| 后缀表达式 | 运算符在操作数后面,也叫逆波兰表达式 | 3 4 2 * + |
前缀和后缀的好处是不需要括号,也不需要考虑优先级。运算顺序完全由位置决定,计算机从左到右扫一遍就能算出来。
手工转换
考试里最常考的是手工转换,掌握两个方法就够。
中缀转后缀:括号法
以 3 + 4 * 2 为例,按运算优先级逐层加括号:
- 先算乘除,给
4 * 2加括号:3 + (4 * 2) - 再算加法,给整式加括号:
(3 + (4 * 2)) - 把每个运算符移到它所在括号的右括号后面:
(3 + (4 2 *) 把 * 移到 4*2 的括号后面
(3 (4 2 *) +) 把 + 移到最外层括号后面
3 4 2 * + 去掉括号结果是 3 4 2 * +。
换成 (3 + 4) * 2 试试:先加括号 ((3 + 4) * 2),运算符后移得到 (3 4 +) 2 *,去掉括号是 3 4 + 2 *。括号改变了顺序,后缀表达式也跟着变。
中缀转前缀:括号法
同理,只是把运算符移到左括号前面,然后去掉括号。
3 + 4 * 2 → 3 + (4 * 2) → (3 + (4 * 2)) → + 3 * 4 2。
栈法:中缀转后缀
括号法适合手算,写程序要用栈。规则是:
- 遇到数字,直接输出。
- 遇到运算符,把栈里优先级不低于它的运算符依次弹出并输出,再把它压栈。
- 遇到左括号,直接压栈。
- 遇到右括号,把栈里直到左括号的运算符全部弹出输出,再把左括号弹掉。
- 扫完后,把栈里剩下的运算符依次弹出输出。
#include <bits/stdc++.h>
using namespace std;
int priority(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0; // 括号
}
int main() {
string s;
cin >> s;
stack<char> st;
for (char c : s) {
if (isdigit(c)) {
cout << c << " "; // 数字直接输出
} else if (c == '(') {
st.push(c);
} else if (c == ')') {
while (!st.empty() && st.top() != '(') {
cout << st.top() << " ";
st.pop();
}
st.pop(); // 弹掉左括号
} else {
while (!st.empty() && st.top() != '(' &&
priority(st.top()) >= priority(c)) {
cout << st.top() << " "; // 优先级高的先输出
st.pop();
}
st.push(c);
}
}
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
return 0;
}这段代码默认每个操作数是一位数字,处理多位数时把连续的 isdigit 攒起来再输出即可。
后缀表达式的求值
后缀表达式求值非常简单,一个栈就能搞定:
- 遇到数字,压栈。
- 遇到运算符,弹出两个数,先弹出的是右操作数,后弹出的是左操作数,算完把结果压回去。
- 扫完后,栈里剩下的唯一一个数就是答案。
#include <bits/stdc++.h>
using namespace std;
int main() {
stack<int> st;
char c;
while (cin >> c) {
if (isdigit(c)) {
st.push(c - '0');
} else {
int b = st.top(); st.pop(); // 先弹出的是右操作数
int a = st.top(); st.pop(); // 后弹出的是左操作数
if (c == '+') st.push(a + b);
else if (c == '-') st.push(a - b);
else if (c == '*') st.push(a * b);
else st.push(a / b);
}
}
cout << st.top() << endl;
return 0;
}以 3 4 2 * + 为例:压 3、压 4、压 2;遇到 *,弹出 2 和 4,算 4 \times 2 = 8 压回去;遇到 +,弹出 8 和 3,算 3 + 8 = 11。答案是 11。
减法、除法要特别注意顺序。3 - 5 对应的后缀是 3 5 -,先弹出的是 5,后弹出的是 3,所以是「后弹出的减先弹出的」。
表达式树
把后缀表达式依次结合,可以把算式画成一棵二叉树,叫表达式树。
- 叶子节点是操作数。
- 内部节点是运算符,左右子树是它的两个操作数。
3 + 4 * 2 的表达式树,根是 +,左子树是 3,右子树是 *,* 的左右是 4 和 2。
三种遍历对应三种表达式:
| 遍历方式 | 得到 |
|---|---|
| 中序遍历 | 中缀表达式(可能要补括号) |
| 前序遍历 | 前缀表达式 |
| 后序遍历 | 后缀表达式 |
这解释了三种表达式之间的本质关系:它们只是同一棵树的不同遍历顺序。记不住转换方法时,画出表达式树再按遍历顺序读一遍,答案就出来了。
中缀表达式求值:双栈法
既然中缀转后缀、再求值要两步,那能不能一步到位?可以,用两个栈:一个存数字,一个存运算符。
规则和「中缀转后缀」几乎一样,只是把「输出」换成了「立刻计算」:
- 遇到数字:压入数字栈(注意多位数要连续读);
- 遇到左括号:压入符号栈;
- 遇到右括号:不断弹出符号栈顶的运算符并计算,直到遇到左括号,然后弹掉左括号;
- 遇到运算符:不断弹出优先级不低于它的运算符并计算,再把它压栈;
- 扫完后:把符号栈里剩下的运算符依次计算完,数字栈顶就是答案。
「计算」这个动作:从数字栈弹出两个数(先出的是右操作数)、从符号栈弹出一个运算符,算完把结果压回数字栈。
#include <bits/stdc++.h>
using namespace std;
int pri(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
// 弹一个运算符、两个数,算完压回去
void calc(stack<long long> &num, stack<char> &op) {
long long b = num.top(); num.pop(); // 先出:右操作数
long long a = num.top(); num.pop(); // 后出:左操作数
char c = op.top(); op.pop();
if (c == '+') num.push(a + b);
else if (c == '-') num.push(a - b);
else if (c == '*') num.push(a * b);
else num.push(a / b);
}
int main() {
string s;
cin >> s;
stack<long long> num;
stack<char> op;
for (int i = 0; i < (int)s.size(); i++) {
if (isdigit(s[i])) {
long long x = 0;
while (i < (int)s.size() && isdigit(s[i])) { // 连续数字组成一个多位数
x = x * 10 + (s[i] - '0');
i++;
}
i--; // 外层 for 还会 i++,这里退一格
num.push(x);
} else if (s[i] == '(') {
op.push('(');
} else if (s[i] == ')') {
while (op.top() != '(') calc(num, op);
op.pop(); // 弹掉左括号
} else {
while (!op.empty() && op.top() != '(' && pri(op.top()) >= pri(s[i])) {
calc(num, op);
}
op.push(s[i]);
}
}
while (!op.empty()) calc(num, op);
cout << num.top() << endl;
return 0;
}为什么要「优先级不低于就弹」而不是「高于才弹」? 因为同优先级的运算要从左到右算。以 3 - 4 - 5 为例:扫描到第二个 - 时,如果只弹「高于」的运算符,栈里的第一个 - 会留下来,最后变成 3 - (4 - 5) = 4,而正确答案是 (3-4)-5 = -6。「不低于」这三个字是这段代码最容易写错的地方。
多位数是另一个坑。 上面的 while (isdigit(...)) 把连续的数字字符攒成一个整数,如果只按单个字符处理,123 会被当成 1、2、3 三个数。
常见易错点
- 后缀表达式求值时,先弹出的是右操作数,顺序反了减法和除法就全错。
- 中缀转后缀时,栈里优先级不低于当前运算符的都要弹出,相等也要弹,否则
3 - 4 - 5会算错。 - 括号法转换时,运算符移到它所属那层括号的外面,不是随便往外挪。
- 表达式树的中序遍历结果不一定是直接可用的中缀表达式,有时需要根据优先级补括号。
- 前缀表达式求值要从右往左扫,后缀表达式从左往右扫。
- 中缀求值时多位数没攒起来。逐字符处理会把
123当成1、2、3三个数。 - 中缀求值用「优先级高于才弹」。必须用「不低于」,否则
3-4-5会算成3-(4-5)=4。 - 后缀/中缀求值时两个操作数弹反了。先弹出的是右操作数,减法和除法写反必错,且加法样例测不出来。
练习
练习 1:后缀表达式求值
在线评测练习:P1418 后缀表达式求值
题目描述
输入一行后缀表达式(逆波兰表达式),操作数为非负整数,运算符只有 +、-、*、/(整除),元素之间用空格分隔。输出表达式的值。
输入格式
输入一行,包含一个后缀表达式,元素之间用一个空格隔开。
输出格式
输出一行一个整数,表示表达式的值。
输入输出样例
输入
3 4 + 2 *输出
14输入
5 1 2 + 4 * + 3 -输出
14数据范围
- 操作数与运算符的总个数不超过
10^5;操作数不超过10^9。 - 保证表达式合法,中间结果与最终结果都在
int范围内,除法不会除以 0。
题目分析
正文已经给出了基本写法,但那道示例是按单个字符读入的,遇到多位数就会错。本题的操作数最大到 10^9,必须按 token 读。
用 cin >> string 逐个读入,cin 会自动跳过空格,天然完成切分:
- token 是
+ - * /之一 → 弹出两个数计算。先弹出的是右操作数; - 否则用
stoll(token)转成数字压栈。
减法和除法的顺序是本题唯一的陷阱。 5 3 - 表示 5 - 3 = 2,而先弹出的是 3。如果写成「先弹出的减后弹出的」,得到 -2,样例 1(只有加法和乘法)却能过——所以一定要用减法或除法的数据自测。
参考代码
练习 2:中缀表达式求值
题目描述
给定一个合法的中缀表达式字符串(只含数字、+、-、*、/、(、),没有空格),求它的值。除法为整除。
输入格式
一行一个字符串,表示中缀表达式。
输出格式
输出一个整数,表示表达式的值。
输入输出样例
输入
3+4*2输出
11输入
(3+4)*2输出
14输入
3-4-5输出
-6数据范围
1 \le |s| \le 10^5,操作数不超过10^9,保证中间结果与结果在long long范围内。
题目分析
正文「中缀表达式求值:双栈法」的完整实现,建议自己先写一遍再对照。
这道题把本章前面所有内容串联起来,值得单独练的四个点:
- 双栈:一个存数字、一个存运算符;
- 优先级与「不低于才弹」:这决定了同级运算是左结合(
3-4-5 = -6而不是 4); - 括号的处理:左括号直接压栈,右括号一路弹到左括号;
- 多位数:连续的数字字符要攒成一个整数。
自测数据建议:至少要覆盖 3+4*2(优先级)、(3+4)*2(括号)、3-4-5(左结合)、10/3(整除)、2*(3+4)-5(混合)这五组。只用前两组测,是测不出「不低于 vs 高于」这个 bug 的。
参考代码
小结
- 中缀表达式符合人的习惯,前缀和后缀表达式不需要括号,计算机处理更方便。
- 中缀转后缀可以用括号法手算,也可以用栈编程实现。
- 后缀表达式求值只需一个栈,遇到运算符就弹出两个数计算。
- 表达式树把三种表达式统一起来:前序、中序、后序遍历分别对应前缀、中缀、后缀。
- 中缀表达式求值可以用双栈一步完成:数字栈 + 符号栈,遇到优先级「不低于」的就先算。
- 同优先级的运算符要从左到右算,这就是「不低于才弹」的原因(
3-4-5的结果是-6)。