栈和队列的应用

本节的几个知识点经常在选择题考察：中序表达式求值、中序转后序、后序表达式求值、入栈出栈序列。

二叉表达式树

二叉表达式树 是一种特殊的二叉树，用于表示算术或逻辑表达式。它的每个 叶子节点 通常存放 操作数（operand，如数字或变量），每个 非叶子节点 存放 操作符（operator，如 +, -, *, /）。

表达式种类

前序表达式（Preorder，波兰表示法）、中序表达式（Infix）和后序表达式（Postorder，逆波兰表示法）是根据二叉表达式树的不同遍历方式得到的表达式结果。具体来说：

前序表达式：前序遍历 得到的序列。
中序表达式：中序遍历 得到的序列。
后序表达式：后序遍历 得到的序列。

这三种表达式的 操作符 和 操作数 间的相对位置有所不同：

表达式类型	描述	示例表达式	对应的公式
前序	操作符位于其操作数之前	`* + A B C`	`(A + B) * C`
中序	操作符位于其两个操作数之间，是最常见的表示法	`(A + B) * C`	`(A + B) * C`
后序	操作符位于其操作数之后	`A B + C *`	`(A + B) * C`

中序表达式求值

中序表达式求值涉及到两个主要的数据结构：操作符栈 与 操作数栈。其核心思路是逐个读取中序表达式的字符，根据字符的类型（操作数、操作符、括号）进行不同的处理，最终得到表达式的值。

初始化两个栈：
- 操作数栈：用来存储数字。
- 操作符栈：用来存储操作符和左括号。
逐个读取中序表达式的字符：
- 如果是 操作数（数字），则直接压入 操作数栈。
- 如果是 左括号，则直接压入 操作符栈。
- 如果是 右括号，则：
  - 从 操作符栈 中弹出一个操作符。
  - 从 操作数栈 中弹出所需的操作数。
  - 执行该操作符对应的运算。
  - 将结果压入 操作数栈。
  - 重复以上步骤，直到从 操作符栈 中弹出一个左括号。
- 如果是操作符（如+、-、*、/等）：
  - 如果 操作符栈 为空，或栈顶是左括号，或当前操作符 优先级 高于栈顶操作符的 优先级，则直接压入 操作符栈。
  - 否则：
    - 从 操作符栈 中弹出一个操作符。
    - 从 操作数栈 中弹出所需的操作数。
    - 执行该操作符对应的运算。
    - 将结果压入 操作数栈。
    - 重复以上步骤，直到满足上述的压栈条件。
处理完所有字符后：
- 如果 操作符栈 不为空，则：
  - 从 操作符栈 中弹出一个操作符。
  - 从 操作数栈 中弹出所需的操作数。
  - 执行该操作符对应的运算。
  - 将结果压入 操作数栈。
  - 重复以上步骤，直到 操作符栈 为空。
得到结果：
- 此时，操作数栈 中仅存一个数字，这就是整个中序表达式的值。

中序表达式求值的过程可以参照以下流程图进行理解：

以表达式 3 + (5 * 2 - 8) 说明计算过程：

步骤	输入字符	操作	操作符栈	数据栈
1	`3`	压入数据栈	空	`3`
2	`+`	压入操作符栈	`+`	`3`
3	`(`	压入操作符栈	`+, (`	`3`
4	`5`	压入数据栈	`+, (`	`3, 5`
5	`*`	压入操作符栈	`+, (, *`	`3, 5`
6	`2`	压入数据栈	`+, (, *`	`3, 5, 2`
7	`-`	`*` 优先级更高，先计算 $5\times2=10$ ，再将 `-` 入栈	`+, (, -`	`3, 10`
8	`8`	压入数据栈	`+, (, -`	`3, 10, 8`
9	`)`	计算 $10-8=2$ ，并弹出左括号	`+`	`3, 2`
10	扫描结束	计算 $3+2=5$	空	`5`

执行轨迹

双栈如何计算中序表达式

逐步点击表达式 3 + (5 × 2 - 8) 的输入，观察操作符栈与数据栈如何变化，以及何时按优先级执行运算。

031+2(354×526-788)9结束

读入 33 是操作数，压入数据栈；操作符栈为空，数据栈为 [3]。

后序表达式求值

后序表达式求值主要依赖一个 操作数栈。其核心思路是逐个读取后序表达式的元素，并根据元素的类型（操作数或操作符）进行处理。

初始化一个操作数栈：
- 用于存储后序表达式中的数字。
逐个读取后序表达式的元素：
- 如果是操作数，则直接压入 操作数栈。
- 如果是操作符（如+、-、*、/等）：
  - 从 操作数栈 中弹出所需的操作数。注意，因为操作符是后置的，所以先弹出的数字是第二操作数，后弹出的是第一操作数。
  - 根据操作符执行相应的运算。
  - 将计算结果压入 操作数栈。
完成后序表达式的读取：
- 操作数栈 中的顶部元素即为整个后序表达式的值。

后序表达式求值的过程可以参照以下流程图进行理解：

flowchart TD
    A[开始: 初始化操作数栈] --> B[读取后序表达式的下一个元素]

    B --> C{是否还有元素?}
    C -->|否| H[栈顶元素即为最终结果]
    H --> I[结束]

    C -->|是| D{当前元素类型?}

    D -->|操作数| E[将操作数压入栈中]
    E --> B

    D -->|操作符| F[从栈中弹出两个操作数<br/>注意: 先弹出的是第二操作数<br/>后弹出的是第一操作数]
    F --> G[执行运算并将结果压入栈中]
    G --> B

    style A fill:#e1f5fe
    style I fill:#c8e6c9
    style D fill:#fff3e0
    style E fill:#f3e5f5
    style F fill:#ffebee
    style G fill:#ffebee
    style H fill:#e8f5e8

以表达式 3 5 2 * 8 - + 说明计算过程：

步骤	输入字符	操作	操作数栈
1	`3`	压入操作数栈	`3`
2	`5`	压入操作数栈	`3, 5`
3	`2`	压入操作数栈	`3, 5, 2`
4	`*`	弹出 $2$ 和 $5$ ，计算 $5\times2=10$ 后压栈	`3, 10`
5	`8`	压入操作数栈	`3, 10, 8`
6	`-`	弹出 $8$ 和 $10$ ，计算 $10-8=2$ 后压栈	`3, 2`
7	`+`	弹出 $2$ 和 $3$ ，计算 $3+2=5$ 后压栈	`5`

对二元运算符，先弹出的值是右操作数，后弹出的值是左操作数；减法和除法尤其不能颠倒。

中序转后序

将中缀表达式转换为后缀表达式的算法思想如下：

初始化一个 操作符栈，从左向右开始扫描中缀表达式；

遇到数字时，加入后缀表达式；
遇到运算符时：
- 若为 （，入栈；
- 若为 ），则依次把栈中的运算符加入后缀表达式中，直到出现 （，从栈中删除 （；
- 若为除括号外的其他运算符
  - 当其 优先级 高于除 （ 以外的栈顶运算符时，直接入栈；
  - 否则从栈顶开始，依次弹出 优先级 高于或等于当前运算符的运算符，直到遇到 优先级 更低的运算符或左括号为止。

中序转后序的过程可以参照以下流程图进行理解：

flowchart TD
    A[开始：初始化操作符栈] --> B[从左向右扫描中缀表达式]
    B --> C{读取下一个字符}

    C -->|数字| D[直接添加到后缀表达式]
    C -->|左括号| E[直接入栈]
    C -->|右括号| F[弹出栈中运算符到后缀表达式]
    C -->|运算符| G{当前运算符优先级 > 栈顶运算符优先级?}

    D --> H{是否扫描完成?}
    E --> H

    F --> I{栈顶是否为左括号?}
    I -->|否| F
    I -->|是| J[弹出左括号但不加入后缀表达式]
    J --> H

    G -->|是| K[直接入栈]
    G -->|否| L[弹出栈顶运算符到后缀表达式]
    L --> M{栈空或栈顶为左括号或优先级更低?}
    M -->|否| L
    M -->|是| N[当前运算符入栈]

    K --> H
    N --> H

    H -->|否| C
    H -->|是| O[弹出栈中所有剩余运算符]
    O --> P[结束：得到后缀表达式]

    style A fill:#e1f5fe,font-size:24px
    style P fill:#c8e6c9,font-size:24px
    style D fill:#fff3e0,font-size:24px
    style E fill:#fce4ec,font-size:24px
    style F fill:#fce4ec,font-size:24px
    style G fill:#f3e5f5,font-size:24px

    classDef default font-size:18px
    classDef largeText font-size:24px
    class A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P largeText

    linkStyle default font-size:22px

以中序表达式 a/b+(c*d-e*f)/g 为例，可以通过如下步骤将其转换为后续表达式：

待处理序列	操作符栈	后缀表达式	当前元素	动作
`/b+(cd-ef)/g`	空	`a`	`a`	`a` 加入后缀表达式
`b+(cd-ef)/g`	`/`	`a`	`/`	`/` 入栈
`+(cd-ef)/g`	`/`	`ab`	`b`	`b` 加入后缀表达式
`+(cd-ef)/g`	空	`ab/`	`+`	`+` 优先级低于栈顶 `/`，先弹出 `/`
`(cd-ef)/g`	`+`	`ab/`	`+`	`+` 入栈
`cd-ef)/g`	`+(`	`ab/`	`(`	左括号入栈
`d-ef)/g`	`+(`	`ab/c`	`c`	`c` 加入后缀表达式
`d-e*f)/g`	`+(*`	`ab/c`	`*`	栈顶为左括号，`*` 入栈
`-e*f)/g`	`+(*`	`ab/cd`	`d`	`d` 加入后缀表达式
`-e*f)/g`	`+(`	`ab/cd*`	`-`	`-` 优先级低于栈顶 ``，先弹出 ``
`e*f)/g`	`+(-`	`ab/cd*`	`-`	栈顶为左括号，`-` 入栈
`*f)/g`	`+(-`	`ab/cd*e`	`e`	`e` 加入后缀表达式
`f)/g`	`+(-*`	`ab/cd*e`	`*`	`*` 优先级高于栈顶 `-`，直接入栈
`)/g`	`+(-*`	`ab/cd*ef`	`f`	`f` 加入后缀表达式
`/g`	`+`	`ab/cdef-`	`)`	弹出左括号之前的 `*`、`-`，再移除左括号
`g`	`+/`	`ab/cdef-`	`/`	`/` 优先级高于栈顶 `+`，直接入栈
扫描结束	`+/`	`ab/cdef-g`	`g`	`g` 加入后缀表达式
完成	空	`ab/cdef-g/+`	—	运算符依次退栈加入表达式

入栈出栈序列

入栈出栈类问题的核心可以被总结为以下两种范式：

给定一个入栈序列，判断哪些出栈序列是不可能的？
给定一个入栈序列，其出栈序列序列有多少种？

这里给出这两个常见问题的解答。

不可能的出栈序列

给定一个入栈序列，其出栈序列可能有很多种，因为一个元素的出栈时间比较灵活，比如它可以一入栈马上出栈，也可以等一会再出栈。要辨别不可能的出栈系列，需要 抓住关键规则：只有 栈顶元素 能够最先出栈。

也就是说，对于下图这种情况，A 被 B 压住了，在出栈序列中，A 一定在 B 的后面。如果某个出栈序列中 A 在 B 的前面，则这种出栈序列是不可能出现的。

卡特兰数

考虑这样一个问题：有 $n$ 个不同的元素（例如 $1,2,\ldots,n$ ），按照固定顺序依次将它们入栈，并且在任意合法时刻可以选择出栈。每个元素都必须恰好入栈一次、出栈一次。我们想知道所有可能的出栈序列共有多少种。

这个问题的答案可以用 卡特兰数（Catalan number） 来表示。卡特兰数的公式如下：

C_n=\frac{1}{n+1}\binom{2n}{n}.

也就是说，上述问题中 $n$ 个元素的所有可能出栈序列数量就是 $C_n$ 。

那么为什么入栈出栈序列总数可以用卡特兰数来表示呢？

我们可以把每一次操作用数字表示：

入栈：记作 +1
出栈：记作 -1

整个过程总共有 $2n$ 次操作，其中有 $n$ 次入栈、 $n$ 次出栈。为了保证操作合法（不能在栈为空时出栈），必须满足：在任意前缀中，出栈次数 不能超过 入栈次数。

这恰好 与卡特兰数的经典定义相对应：卡特兰数计数的就是符合类似限制的序列数量。因此，入栈出栈序列数量正好是 $C_n$ 。

卡特兰数不仅出现在入栈出栈序列中，还常 出现在很多等价问题中，例如：

二叉树计数：给定 $n$ 个结点，不同形态二叉树的数量为 $C_n$ 。
括号匹配： $n$ 对括号的合法匹配序列数量也为 $C_n$ 。例如，当 $n=2$ 时，合法序列有：
```
()()   (())
```

表达式处理的判定规则

优先级、结合性与括号

双栈求值和中缀转后缀时，不能只比较“谁的优先级更高”，还要看同一优先级的运算符怎样结合。以常见二元运算为例， $+$ 、 $-$ 、 $\times$ 、 $/$ 都是左结合：读到新的同级运算符时，应先计算或输出栈顶的旧运算符，再把新的运算符入栈。括号只控制局部范围：左括号永远直接入栈，右括号只弹出到左括号为止，左括号本身既不参加运算，也不写入后缀表达式。

情形	扫描到当前运算符后的处理	容易误判的点
栈顶优先级更高	栈顶先退栈并完成一次归约	不能把高优先级运算符留到低优先级运算符之后
优先级相同且左结合	栈顶先退栈	a-b-c 应解释为 (a-b)-c
栈顶是左括号	当前运算符直接入栈	左括号不是普通的最低优先级运算符
题目出现右结合运算符	依题设决定同级时是否退栈	例如幂运算若规定右结合，a^b^c 应按 a^(b^c) 处理

负号也需要先由词法位置判断：出现在表达式开头、左括号后或另一个运算符后时，可能表示一元负号；出现在操作数之后时才是二元减法。408 的手算题通常会把操作数作为完整记号给出，但看到负数时不能机械地把它拆成“空操作数减正数”。

合法后缀式与出栈序列的快速检验

对只含二元运算符的后缀表达式，扫描时遇到操作数就把“可用操作数数”加一，遇到运算符就消费两个操作数并产生一个结果，等价于该数减一。因此，任一非空前缀都必须满足“操作数数严格大于运算符数”，扫描结束时必须恰好满足

\text{操作数个数}=\text{二元运算符个数}+1.

若某一步想弹出两个数而栈中不足两个数，或结束时栈中不止一个值，该后缀式都不合法。减法、除法还要严格按“先弹出的是右操作数、后弹出的是左操作数”恢复次序。

判断给定出栈序列是否可能，不必枚举所有卡特兰数情况。按目标出栈序列从左到右处理：若栈顶等于下一个目标元素就弹出；否则按固定入栈序列不断压栈，直到栈顶匹配或输入已经用尽。后者仍不匹配便说明不可能。每个元素至多入栈、出栈一次，所以该判定的时间和辅助空间都是 $O(n)$ 。

卡特兰数也可由“第一个入栈元素何时最后出栈”理解。若它把其余元素划分为左右两个独立的合法子过程，则有

C_0=1,\qquad C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}.

这个递推说明卡特兰数不是“任意入、出栈操作数”的简单排列数；每一个中间前缀都必须满足栈不为空的约束。