通过表达式树、表达式求值与转换、括号匹配、入栈出栈序列和卡特兰数掌握栈的应用，并理解队列在调度和广度优先处理中的作用。

# 一、表达式树与三种表达式

表达式树的叶结点是操作数，内部结点是操作符；子树先于父结点计算。对于表达式 $(A+B)\times C$：

1
2
3
4
5

flowchart TB
    M["×"] --> P["+"]
    M --> C["C"]
    P --> A["A"]
    P --> B["B"]

对同一棵表达式树进行不同遍历，可得到三种写法：

中缀表达式的真实计算顺序依赖优先级和括号；前缀、后缀表达式不需要括号便能唯一确定二元运算顺序。

# 二、中缀表达式求值

中缀求值维护两个栈：

• 操作数栈：保存尚未参与运算的数字或已算出的子表达式值；
• 操作符栈：保存运算符和左括号。

当需执行运算时，必须先弹出右操作数 $B$，再弹出左操作数 $A$，计算 $A\mathbin{\mathrm{op}}B$ 并把结果压回操作数栈。对于减法、除法，这个顺序绝不能颠倒。

处理从左到右扫描到的记号时：

1. 操作数直接压入操作数栈。
2. 左括号直接压入操作符栈。
3. 右括号到来时，连续计算直到弹出与之匹配的左括号；左括号不参与计算。
4. 普通运算符到来时，若栈顶运算符优先级更高，或优先级相同且当前运算符左结合，则先计算栈顶运算符；之后再将当前运算符入栈。
5. 扫描结束后，计算操作符栈中剩余运算符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

flowchart TD
    S[读取下一个记号] --> K{记号类型}
    K -->|操作数| A[压入操作数栈]
    K -->|左括号| B[压入操作符栈]
    K -->|右括号| C[计算直到弹出左括号]
    K -->|普通运算符| D[按优先级和结合性弹出并计算]
    A --> S
    B --> S
    C --> S
    D --> S
    S --> E{是否扫描结束}
    E -->|否| K
    E -->|是| F[计算所有剩余运算符]
    F --> G[操作数栈唯一元素即结果]

# 三、后缀表达式求值与中缀转后缀

# 1. 后缀表达式求值

后缀表达式只需一个操作数栈：

1. 读到操作数，压栈；
2. 读到二元操作符，先弹出 $B$，再弹出 $A$；
3. 计算 $A\mathbin{\mathrm{op}}B$，把结果压栈；
4. 扫描结束时，栈中应恰有一个元素，即表达式值。

例如后缀表达式 $3\ 5\ 2\ \times\ 8\ -\ +$ 的计算过程为：

# 2. 中缀转后缀

转换时只需要操作符栈，操作数直接进入输出序列：

• 操作数：直接输出；
• 左括号：压栈；
• 右括号：弹出并输出直到左括号，随后丢弃左括号；
• 普通操作符：弹出优先级高于它的运算符；对左结合运算符，还要弹出优先级相等的运算符；最后把当前运算符压栈；
• 扫描结束：把剩余运算符依次输出。

例如

$$a/b+(c\times d-e\times f)/g$$

转换为后缀式：

$$a\ b\ /\ c\ d\ \times\ e\ f\ \times\ -\ g\ /\ +.$$

指数运算若作为右结合运算符，应与加减乘除的左结合规则分开处理；题目没有说明时，通常只讨论 $+,-,\times,/$。

# 四、括号匹配

括号匹配是栈的直接应用。扫描表达式：

1. 遇到左括号 $($、$[$、$\{$，压栈；
2. 遇到右括号时，栈必须非空，且栈顶必须是对应的左括号；随后弹栈；
3. 扫描结束时，栈必须为空。

任一时刻若右括号无法匹配，或扫描结束后仍有左括号残留，序列均不合法。只检查扫描过程中是否出错还不够，必须检查最终栈是否为空。

# 五、入栈出栈序列

给定固定入栈序列和候选出栈序列，判断合法性的可靠方法是模拟：

1. 依次把尚未入栈的元素压栈；
2. 每次压栈后，只要栈顶等于候选出栈序列的当前元素，就立即弹出；
3. 最后若所有元素均已按候选序列弹出，则合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#define MAX_SIZE 100

bool IsValidPopSequence(const int push[], const int pop[], int n) {
    int stack[MAX_SIZE];
    int top = -1;
    int j = 0;

    for (int i = 0; i < n; i++) {
        stack[++top] = push[i];
        while (top != -1 && j < n && stack[top] == pop[j]) {
            top--;
            j++;
        }
    }
    return j == n;
}

# 卡特兰数

若 $n$ 个不同元素以固定次序进栈，允许在任意合法时刻出栈，则不同合法出栈序列的数目为第 $n$ 个卡特兰数：

$$\boxed{C_n=\frac{1}{n+1}C_{2n}^{n} =\frac{(2n)!}{n!(n+1)!}}.$$

其中 $C_{2n}^{n}$ 是组合数。递推关系为

$$C_0=1,\qquad C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}\quad(n\ge1).$$

本质原因是任意时刻出栈次数不能超过入栈次数；它与合法括号序列的 “任意前缀中右括号数不超过左括号数” 是同一个约束。因此 $n$ 对括号的合法序列数、$n$ 个结点的不同二叉树形态数也都是 $C_n$。

# 六、队列的典型应用

队列适合 “先到先处理” 的场景：

• 任务调度与缓冲：按到达顺序处理请求、打印任务或消息；
• 广度优先搜索：先入队的结点先扩展，因此按距离层次访问；
• 层序遍历：二叉树中结点出队时，把其孩子按次序入队。

队列不保证 “最新任务优先”；若需要按优先级选择任务，应使用优先队列而不是普通队列。

# 七、考场检查清单

1. 表达式计算弹出两个操作数时，先弹出的是右操作数。
2. 中缀转后缀的括号不输出；右括号只触发退栈。
3. 判括号匹配时，结束后仍要检查栈是否为空。
4. 入栈出栈序列判断以模拟为准，不能只凭局部大小关系猜测。
5. 卡特兰数的前提是固定入栈次序、每个元素恰好进栈和出栈一次、且不允许空栈出栈。