Skip to content

表达式与表达式树

中缀、前缀、后缀表达式的互相转换与求值,以及表达式树。

Updated View as Markdown

我们平时写的算式,比如 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 为例,按运算优先级逐层加括号:

  1. 先算乘除,给 4 * 2 加括号:3 + (4 * 2)
  2. 再算加法,给整式加括号:(3 + (4 * 2))
  3. 把每个运算符移到它所在括号的右括号后面:
(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。

栈法:中缀转后缀

括号法适合手算,写程序要用栈。规则是:

  1. 遇到数字,直接输出。
  2. 遇到运算符,把栈里优先级不低于它的运算符依次弹出并输出,再把它压栈。
  3. 遇到左括号,直接压栈。
  4. 遇到右括号,把栈里直到左括号的运算符全部弹出输出,再把左括号弹掉。
  5. 扫完后,把栈里剩下的运算符依次弹出输出。
#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 攒起来再输出即可。

后缀表达式的求值

后缀表达式求值非常简单,一个栈就能搞定:

  1. 遇到数字,压栈。
  2. 遇到运算符,弹出两个数,先弹出的是右操作数,后弹出的是左操作数,算完把结果压回去。
  3. 扫完后,栈里剩下的唯一一个数就是答案。
#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。

三种遍历对应三种表达式:

遍历方式 得到
中序遍历 中缀表达式(可能要补括号)
前序遍历 前缀表达式
后序遍历 后缀表达式

这解释了三种表达式之间的本质关系:它们只是同一棵树的不同遍历顺序。记不住转换方法时,画出表达式树再按遍历顺序读一遍,答案就出来了。

中缀表达式求值:双栈法

既然中缀转后缀、再求值要两步,那能不能一步到位?可以,用两个栈:一个存数字,一个存运算符。

规则和「中缀转后缀」几乎一样,只是把「输出」换成了「立刻计算」:

  1. 遇到数字:压入数字栈(注意多位数要连续读);
  2. 遇到左括号:压入符号栈;
  3. 遇到右括号:不断弹出符号栈顶的运算符并计算,直到遇到左括号,然后弹掉左括号;
  4. 遇到运算符:不断弹出优先级不低于它的运算符并计算,再把它压栈;
  5. 扫完后:把符号栈里剩下的运算符依次计算完,数字栈顶就是答案。

「计算」这个动作:从数字栈弹出两个数(先出的是右操作数)、从符号栈弹出一个运算符,算完把结果压回数字栈。

#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 范围内。

题目分析

正文「中缀表达式求值:双栈法」的完整实现,建议自己先写一遍再对照。

这道题把本章前面所有内容串联起来,值得单独练的四个点:

  1. 双栈:一个存数字、一个存运算符;
  2. 优先级与「不低于才弹」:这决定了同级运算是左结合(3-4-5 = -6 而不是 4);
  3. 括号的处理:左括号直接压栈,右括号一路弹到左括号;
  4. 多位数:连续的数字字符要攒成一个整数。

自测数据建议:至少要覆盖 3+4*2(优先级)、(3+4)*2(括号)、3-4-5(左结合)、10/3(整除)、2*(3+4)-5(混合)这五组。只用前两组测,是测不出「不低于 vs 高于」这个 bug 的。

参考代码

小结

  • 中缀表达式符合人的习惯,前缀和后缀表达式不需要括号,计算机处理更方便。
  • 中缀转后缀可以用括号法手算,也可以用栈编程实现。
  • 后缀表达式求值只需一个栈,遇到运算符就弹出两个数计算。
  • 表达式树把三种表达式统一起来:前序、中序、后序遍历分别对应前缀、中缀、后缀。
  • 中缀表达式求值可以用双栈一步完成:数字栈 + 符号栈,遇到优先级「不低于」的就先算。
  • 同优先级的运算符要从左到右算,这就是「不低于才弹」的原因(3-4-5 的结果是 -6)。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close