栈和队列的应用
二叉表达式树
二叉表达式树 是一种特殊的二叉树,用于表示算术或逻辑表达式。它的每个 叶子节点 通常存放 操作数(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 | - | * 优先级 高于 - ,* 出栈计算后,将 - 入栈 | +, (, - | 3, 10 |
8 | 8 | 压入数据栈 | +, (, - | 3, 10, 8 |
9 | ) | 处理到 ( 之前的所有操作符 | + | 3, 2 |
10 | 用 + 运算符计算 | 5 |
后序表达式求值
后序表达式求值主要依赖一个 操作数栈。其核心思路是逐个读取后序表达式的元素,并根据元素的类型(操作数或操作符)进行处理。
- 初始化一个 操作数栈:
- 用于存储后序表达式中的数字。
- 逐个读取后序表达式的元素:
- 如果是操作数,则直接压入 操作数栈。
- 如果是操作符(如+、-、*、/等):
- 从 操作数栈 中弹出所需的操作数。注意,因为操作符是后置的,所以先弹出的数字是第二操作数,后弹出的是第一操作数。
- 根据操作符执行相应的运算。
- 将计算结果压入 操作数栈。
- 完成后序表达式的读取:
- 操作数栈 中的顶部元素即为整个后序表达式的值。
后序表达式求值的过程可以参照以下流程图进行理解:
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 | * | 弹出两个操作数并相乘,结果压入 操作数栈 | 3, 10 |
5 | 8 | 压入 操作数栈 | 3, 10, 8 |
6 | - | 弹出两个操作数并相减,结果压入 操作数栈 | 3, 2 |
7 | + | 弹出两个操作数并相加,结果压入 操作数栈 | 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
为例,可以通过如下步骤将其转换为后续表达式:
待处理序列 | 栈 | 后缀表达式 | 当前扫描元素 | 动作 |
---|---|---|---|---|
a/b+(c*d-e*f)/g | a | a 加入后缀表达式 | ||
/b+(c*d-e*t)/g | a | / | / 入栈 | |
b+(c*d-e*f)/g | / | a | b | b 加入后缀表达式 |
+(c*d-e*f)/g | / | ab | + | + 优先级 低于栈顶的 / ,弹出 / |
+(c*d-e*f)/g | ab/ | + | + 入栈 | |
(c*d-e*f)/g | + | ab/ | ( | ( 入栈 |
c*d-e*f)/g | +( | ab/ | c | c 加入后缀表达式 |
*d-e*f)/g | +( | ab/c | * | 栈顶为 ( ,* 入栈 |
d-e*t)/g | +(* | ab/c | d | d 加入后缀表达式 |
-e*f)/g | +(* | ab/cd | - | - 先级低于栈顶的 * ,弹出 * |
-e*f)/g | +( | ab/cd* | - | 栈顶为 ( ,- 入栈 |
e*t)/g | +(- | ab/cd* | e | e 加入后缀表达式 |
*f)/g | +(- | ab/cd*e | * | * 优先级 高于栈顶的 - , * 入栈 |
f)/g | +(-* | ab/cd*e | f | f 加入后缀表达式 |
)/g | +(-* | ab/cd*ef | ) | 把栈中 ( 之前的符号加入表达式 |
/g | + | ab/cd*ef*- | / | / 优先级 高于栈顶的 + ,/ 入栈 |
g | +/ | ab/cd*ef*- | g | g 加入后缀表达式 |
+/ | ab/cd*ef*-g | 扫描完毕,运算符依次退栈加入表达式 | ||
ab/cd*ef*-g/+ | 完成 |
入栈出栈序列
入栈出栈是常考的问题,这类问题的核心可以被总结为以下两种范式:
- 给定一个入栈序列,判断哪些出栈序列是不可能的?
- 给定一个入栈序列,其出栈序列序列有多少种?
这里给出这两个常见问题的解答。
不可能的出栈序列
给定一个入栈序列,其出栈序列可能有很多种,因为一个元素的出栈时间比较灵活,比如它可以一入栈马上出栈,也可以等一会再出栈。要辨别不可能的出栈系列,需要 抓住关键规则:只有 栈顶元素 能够最先出栈。
也就是说,对于下图这种情况,A 被 B 压住了,在出栈序列中,A 一定在 B 的后面。如果某个出栈序列中 A 在 B 的前面,则这种出栈序列是不可能出现的。
卡特兰数
考虑这样一个问题:有 $n$ 个不同的元素(例如 $1,2,\cdots,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$ 时,合法的序列有:
()() (())