---
title: "表达式与表达式树"
description: "中缀、前缀、后缀表达式的互相转换与求值，以及表达式树。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 表达式与表达式树

我们平时写的算式，比如 `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. 扫完后，把栈里剩下的运算符依次弹出输出。

```cpp
#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. 扫完后，栈里剩下的唯一一个数就是答案。

```cpp
#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. 扫完后：把符号栈里剩下的运算符依次计算完，数字栈顶就是答案。

**「计算」这个动作**：从数字栈弹出两个数（先出的是右操作数）、从符号栈弹出一个运算符，算完把结果压回数字栈。

```cpp
#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 后缀表达式求值](https://dailyup.run/tasks/502)

#### 题目描述

输入一行后缀表达式（逆波兰表达式），操作数为非负整数，运算符只有 `+`、`-`、`*`、`/`（整除），元素之间用空格分隔。输出表达式的值。

#### 输入格式

输入一行，包含一个后缀表达式，元素之间用一个空格隔开。

#### 输出格式

输出一行一个整数，表示表达式的值。

#### 输入输出样例

输入

```
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（只有加法和乘法）却能过——**所以一定要用减法或除法的数据自测**。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/expression/index.md

### 练习 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 的。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/expression/index.md

## 小结

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

Source: https://cppguide.xyz/ds/expression/index.mdx
