栈和队列的应用

二叉表达式树

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

表达式中的每一个 运算 都对应二叉树中的一个 内部节点，该运算所作用的两个对象分别对应它的 左子树 和 右子树。

例如，对于表达式：

(3 + 4) × (5 - 2) ÷ 7

可以按照运算顺序拆分：

1. 先计算 3 + 4
2. 再计算 5 - 2
3. 然后计算 (3 + 4) × (5 - 2)
4. 最后计算 ((3 + 4) × (5 - 2)) ÷ 7

因此对应的表达式树中：

• 根节点为 ÷
• 根节点的左子树表示 (3 + 4) × (5 - 2)
• 根节点的右子树为操作数 7
• 左子树的根节点为 ×
• × 的左右子树分别表示 3 + 4 和 5 - 2
• 数字 3、4、5、2、7 都是叶子节点

可以发现，表达式树描述的是表达式的运算顺序，而不是书写顺序。越靠近叶子节点的运算越先进行，越靠近根节点的运算越后进行，也就是 子表达式先计算，再逐层合成为整个表达式。

由于表达式树具有明确的层次结构，因此对它采用不同的遍历方式，就能够得到不同形式的表达式。

表达式种类

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

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

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

中序表达式求值

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

在讲述中序表达式的求值流程之前，首先说明一下使用 操作数栈 和 操作符栈 的 基本计算单元：

• 从 操作符栈 中 弹出一个操作符 op。
• 从 操作数栈 中弹出 两个操作数 B 和 A。
• 执行该操作符对应的运算，得到结果 res = A op B。
• 将结果 res 压入 操作数栈。

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

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

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

后序表达式求值

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

1. 初始化一个 操作数栈：
   • 用于存储后序表达式中的数字。
2. 逐个读取后序表达式的元素：
   • 如果是操作数，则直接压入 操作数栈。
   • 如果是操作符（如+、-、*、/等）：
     • 从 操作数栈 中弹出所需的操作数。注意，因为操作符是后置的，所以先弹出的数字是第二操作数，后弹出的是第一操作数。
     • 根据操作符执行相应的运算。
     • 将计算结果压入 操作数栈。
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 - + 说明计算过程：

中序转后序

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

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

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

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

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 为例，可以通过如下步骤将其转换为后续表达式：

入栈出栈序列

入栈出栈序列问题是栈中最经典的一类题目。

在这类问题中，通常会给定一个 入栈序列（例如 1,2,3,4,5），元素必须按照该顺序依次入栈。在每完成一次入栈操作后，可以选择立即将 栈顶元素 出栈，也可以继续执行下一次入栈操作。整个过程中，栈始终遵循 后进先出（LIFO） 的规则，因此只有当前栈顶元素才能出栈。

例如，对于入栈序列 1,2,3，可以按如下顺序进行操作：

入栈 1 → 入栈 2 → 出栈 2 → 入栈 3 → 出栈 3 → 出栈 1

最终得到的出栈序列为：

2,3,1

由于每次入栈后都可以灵活选择是否立即出栈，因此对于同一个入栈序列，通常会对应多个不同的出栈序列。

这类题目通常可以归纳为以下两种：

• 给定一个入栈序列，判断某个出栈序列是否可能出现。
• 给定一个入栈序列，求一共可以产生多少种不同的出栈序列。

下面分别介绍这两类问题的解法。

不可能的出栈序列

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

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

卡特兰数

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

这个问题的答案可以用 卡特兰数（Catalan Number） 表示。

卡特兰数的 公式 为：

因此， $n$ 个元素能够形成的合法出栈序列数量就是：

那么，为什么入栈出栈序列的数量恰好是卡特兰数呢？

可以把整个入栈、出栈过程看成一个长度为 $2n$ 的操作序列：

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

由于共有 $n$ 次入栈和 $n$ 次出栈，因此整个序列中必然有 $n$ 个 +1 和 $n$ 个 -1。

与此同时，为了保证栈操作合法，还必须满足一个重要约束：

在任意时刻，出栈次数不能超过入栈次数，否则就会出现空栈出栈。

因此，一个合法的出栈序列实际上就对应着一个满足上述约束的 +1/-1 序列。

而卡特兰数的经典定义正是用于计数满足这一约束的序列数量，因此合法出栈序列的总数就是卡特兰数。

除了闭式公式之外，卡特兰数还有一个非常重要的 递归关系 ：

它表示：一个规模为 $n$ 的问题，可以划分为两个规模更小、且彼此独立的子问题，其方案数相乘，再对所有划分方式求和。

这个递推关系解释了为什么许多看似不同的问题最终都会得到同一个答案——它们都具有相同的递归结构。

卡特兰数不仅出现在入栈出栈序列中，还会出现在许多本质相同的计数问题中。

不同形态二叉树计数

给定 n 个互不相同的节点，若节点的值已经固定，只考虑二叉树的结构形态（不考虑节点在平面上的绘制方式），则能够构造出的不同二叉树数量为 $C_n$ 。

原因在于：任选一个节点作为根节点后，它左边的节点只能构成左子树，右边的节点只能构成右子树。若左子树有 $i$ 个节点，则右子树必然有 $n-1-i$ 个节点，因此不同二叉树的数量满足：

这与卡特兰数的递推关系完全一致。

例如，当 n=3 时，共有 5 种不同形态的二叉树，因此：

合法括号序列计数

给定 n 对括号，要求生成所有合法的括号序列。所谓合法，是指从左到右扫描整个序列时，任意前缀中左括号的数量都不少于右括号，并且最终左右括号数量相等。

例如，当 n=2 时，共有两种合法序列：

()()
(())

因此：

之所以也是卡特兰数，是因为每个合法括号序列都可以唯一写成：

( 合法序列A ) 合法序列B

设括号 () 内部包含 $i$ 对括号，则后面剩余 $n-1-i$ 对括号，因此方案数同样满足：

这与卡特兰数的递推关系完全一致。

可以发现，虽然入栈出栈序列、不同形态二叉树、合法括号序列看起来属于完全不同的问题，但它们都具有相同的递归结构，因此满足同一个递推关系，最终都可以用 卡特兰数（Catalan Number） 来计数。