Appearance
408
数据结构
DS-03-05 栈和队列的应用（表达式求值/括号匹配/递归）
一、定位信息
| 项目 | 内容 |
|---|---|
| 所属圈层 | 核心层 |
| 考点热度 | H级（高频重点） — 表达式求值（中缀转后缀、后缀表达式计算）是408大题的经典考点，括号匹配和递归也常出现在选择题中，综合分值可达8–12分 |
| 前置知识回顾 | 需掌握"栈的基本概念与实现"（DS-03-01），理解栈的后进先出特性；需具备基本的数学表达式常识（运算符优先级、结合性） |
| 知识网络定位 | 本单元是栈的直接应用，体现了栈在实际问题中的核心价值；递归与栈的关系为后续理解深度优先搜索（DFS）、回溯算法等奠定基础 |
二、知识点讲解
2.1 表达式的三种形式
同一个数学表达式可以有三种等价的书写形式：
| 形式 | 运算符位置 | 示例 |
|---|---|---|
| 中缀表达式 | 运算符在操作数之间 | |
| 前缀表达式（波兰式） | 运算符在操作数之前 | |
| 后缀表达式（逆波兰式） | 运算符在操作数之后 |
直观理解：
- 中缀是我们日常书写方式，但计算机难以直接处理（需要考虑优先级和括号）
- 后缀表达式不需要括号，运算符的顺序本身就隐含了优先级，计算机可以从左到右直接求值
2.2 中缀表达式转后缀表达式（栈的应用）
算法思路：使用一个运算符栈，从左到右扫描中缀表达式：
- 操作数：直接输出
- 左括号
(：压入栈 - 右括号
)：依次弹出栈顶运算符并输出，直到遇到左括号（左括号弹出但不输出） - 运算符：比较当前运算符与栈顶运算符的优先级：
- 若当前优先级 > 栈顶优先级：压入栈
- 若当前优先级 ≤ 栈顶优先级：弹出栈顶并输出，再将当前运算符压入栈
- 扫描结束：将栈中剩余运算符依次弹出并输出
运算符优先级（从高到低）：
| 优先级 | 运算符 |
|---|---|
| 3（最高） | (（入栈时优先级最高） |
| 2 | *, / |
| 1 | +, - |
| 0（最低） | (（栈内时优先级最低） |
关键细节：左括号
(在栈外（等待入栈时）优先级最高，但在栈内（与其他运算符比较时）优先级最低。这样可以保证括号内的运算符不会被提前弹出。
c
// 将中缀表达式infix转换为后缀表达式postfix
// infix以'\0'结尾，运算数和运算符之间用空格分隔
void InfixToPostfix(char *infix, char *postfix) {
SqStack S; // 运算符栈
InitStack(S);
int i = 0, k = 0; // i扫描infix，k写入postfix
char ch;
while (infix[i] != '\0') {
ch = infix[i];
if (ch是操作数) {
// 操作数直接输出到postfix
while (infix[i]是数字或字母)
postfix[k++] = infix[i++];
postfix[k++] = ' '; // 空格分隔
}
else if (ch == '(') {
Push(S, ch); // 左括号入栈
i++;
}
else if (ch == ')') {
// 右括号：弹出直到遇到左括号
ElemType top;
while (!StackEmpty(S)) {
Pop(S, top);
if (top == '(') break; // 左括号弹出但不输出
postfix[k++] = top;
postfix[k++] = ' ';
}
i++;
}
else if (ch是运算符) {
// 比较优先级，弹出优先级>=当前的栈顶运算符
ElemType top;
while (!StackEmpty(S)) {
GetTop(S, top);
if (top == '(') break; // 遇到左括号停止
if (Priority(top) >= Priority(ch)) {
Pop(S, top); // 弹出并输出
postfix[k++] = top;
postfix[k++] = ' ';
} else {
break; // 栈顶优先级更低，停止
}
}
Push(S, ch); // 当前运算符入栈
i++;
}
}
// 扫描结束，弹出栈中剩余运算符
ElemType top;
while (!StackEmpty(S)) {
Pop(S, top);
postfix[k++] = top;
postfix[k++] = ' ';
}
postfix[k] = '\0'; // 字符串结束符
}示例：将 转为后缀表达式
| 步骤 | 读入 | 栈 | 输出 |
|---|---|---|---|
| 1 | 9 | 9 | |
| 2 | + | + | 9 |
| 3 | ( | +( | 9 |
| 4 | 3 | +( | 9 3 |
| 5 | - | +(- | 9 3 |
| 6 | 1 | +(- | 9 3 1 |
| 7 | ) | + | 9 3 1 - |
| 8 | * | +* | 9 3 1 - |
| 9 | 3 | +* | 9 3 1 - 3 |
| 10 | + | + | 9 3 1 - 3 * + |
| 11 | 10 | + | 9 3 1 - 3 * + 10 |
| 12 | / | +/ | 9 3 1 - 3 * + 10 |
| 13 | 2 | +/ | 9 3 1 - 3 * + 10 2 |
| 结束 | 9 3 1 - 3 * + 10 2 / + |
后缀表达式：9 3 1 - 3 * + 10 2 / +
2.3 后缀表达式求值（栈的应用）
算法思路：使用一个操作数栈，从左到右扫描后缀表达式：
- 操作数：压入栈
- 运算符：依次弹出两个操作数（先弹出的是右操作数），执行运算，将结果压入栈
- 扫描结束：栈中唯一元素即为表达式的值
c
// 后缀表达式求值
// postfix中操作数和运算符用空格分隔
int EvaluatePostfix(char *postfix) {
SqStack S; // 操作数栈
InitStack(S);
int i = 0;
int operand1, operand2; // 两个操作数
while (postfix[i] != '\0') {
if (postfix[i]是数字) {
// 解析多位数并入栈
int num = 0;
while (postfix[i] >= '0' && postfix[i] <= '9') {
num = num * 10 + (postfix[i] - '0');
i++;
}
Push(S, num); // 操作数入栈
}
else if (postfix[i]是运算符) {
Pop(S, operand2); // 先弹出的是右操作数
Pop(S, operand1); // 后弹出的是左操作数
switch (postfix[i]) {
case '+': Push(S, operand1 + operand2); break;
case '-': Push(S, operand1 - operand2); break;
case '*': Push(S, operand1 * operand2); break;
case '/': Push(S, operand1 / operand2); break;
}
i++;
}
else {
i++; // 跳过空格
}
}
int result;
Pop(S, result); // 栈中唯一元素即为结果
return result;
}示例：求后缀表达式 9 3 1 - 3 * + 10 2 / + 的值
| 步骤 | 读入 | 操作 | 栈 |
|---|---|---|---|
| 1 | 9 | 入栈 | [9] |
| 2 | 3 | 入栈 | [9, 3] |
| 3 | 1 | 入栈 | [9, 3, 1] |
| 4 | - | 3-1=2，入栈 | [9, 2] |
| 5 | 3 | 入栈 | [9, 2, 3] |
| 6 | * | 2*3=6，入栈 | [9, 6] |
| 7 | + | 9+6=15，入栈 | [15] |
| 8 | 10 | 入栈 | [15, 10] |
| 9 | 2 | 入栈 | [15, 10, 2] |
| 10 | / | 10/2=5，入栈 | [15, 5] |
| 11 | + | 15+5=20，入栈 | [20] |
结果：20
2.4 括号匹配
问题：给定一个括号序列（如 ({[()]})），判断括号是否匹配。
算法思路：使用一个括号栈：
- 遇到左括号（
(、[、{）：压入栈 - 遇到右括号（
)、]、}）：- 若栈空：不匹配
- 若栈顶左括号与当前右括号类型匹配：弹出栈顶，继续
- 若不匹配：返回失败
- 扫描结束后，若栈空则匹配成功，否则有未匹配的左括号
c
bool BracketMatch(char *str) {
SqStack S;
InitStack(S);
for (int i = 0; str[i] != '\0'; i++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
Push(S, str[i]); // 左括号入栈
}
else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
if (StackEmpty(S)) return false; // 栈空，右括号无匹配
ElemType top;
Pop(S, top);
// 检查括号类型是否匹配
if (str[i] == ')' && top != '(') return false;
if (str[i] == ']' && top != '[') return false;
if (str[i] == '}' && top != '{') return false;
}
}
return StackEmpty(S); // 栈空则全部匹配
}2.5 递归与栈的关系
递归 是函数直接或间接调用自身的过程。递归的执行依赖于系统调用栈（函数调用栈）。
每次函数调用时，系统将以下信息压入调用栈：
- 返回地址：调用完成后回到哪里继续执行
- 局部变量：函数内的局部变量
- 参数：传递给函数的参数
- 返回值：函数的返回值
这称为一个栈帧（Stack Frame）。
示例：阶乘函数
c
int Factorial(int n) {
if (n <= 1) return 1; // 递归出口（基线条件）
return n * Factorial(n - 1); // 递归调用
}调用 Factorial(4) 时调用栈的变化：
调用 Factorial(4)：栈 [F(4)]，需要 4 × F(3)
调用 Factorial(3)：栈 [F(4), F(3)]，需要 3 × F(2)
调用 Factorial(2)：栈 [F(4), F(3), F(2)]，需要 2 × F(1)
调用 Factorial(1)：栈 [F(4), F(3), F(2), F(1)]，返回 1
返回 Factorial(2)：栈 [F(4), F(3), F(2)]，返回 2×1=2
返回 Factorial(3)：栈 [F(4), F(3)]，返回 3×2=6
返回 Factorial(4)：栈 [F(4)]，返回 4×6=24递归转非递归：可以用显式栈模拟系统调用栈，将递归算法转换为非递归算法。这在408大题中偶尔出现。
递归的关键要素：
- 递归出口（基线条件）：不再递归的条件，防止无限递归
- 递归体：将问题分解为更小的子问题
- 趋向出口：每次递归调用必须向递归出口靠近
三、记忆与理解辅助
技巧1：后缀表达式求值口诀
"遇到数就入栈，遇到符号就运算；先出的是右操作数，后出的是左操作数"
技巧2：中缀转后缀的优先级处理口诀
"栈外高优先入栈，栈外低先弹再入；遇到括号特殊处理，左括号入栈优先级最高"
技巧3：栈和队列应用场景对比表
| 应用场景 | 使用的数据结构 | 原因 |
|---|---|---|
| 表达式求值 | 栈（操作数栈+运算符栈） | 运算符需要后进先出处理优先级 |
| 括号匹配 | 栈 | 最近的左括号应最先与右括号匹配 |
| 函数递归 | 系统调用栈 | 最后调用的函数最先返回 |
| 浏览器前进/后退 | 两个栈 | 后退栈和前进栈配合使用 |
| BFS层序遍历 | 队列 | 先访问的节点其邻居先入队 |
| 打印任务排队 | 队列 | 先提交的任务先打印 |
技巧4：中缀、前缀、后缀的转换规则
| 转换 | 方法 |
|---|---|
| 中缀→后缀 | 运算符栈，按优先级弹出 |
| 中缀→前缀 | 类似后缀，但从右到左扫描，结果反转 |
| 后缀求值 | 操作数栈，遇运算符弹两个数计算 |
| 前缀求值 | 操作数栈，从右到左扫描，遇运算符弹两个数计算 |
四、例题与精解
例题1（基础）
题目：将中缀表达式 转换为后缀表达式。
命题意图：考查中缀转后缀的基本方法，涉及不同优先级运算符的处理。
审题分析：
- 已知：中缀表达式
- 求解：对应的后缀表达式
- 运算符优先级：（高） > （低）
解题思路： 按中缀转后缀算法，逐一处理每个符号。
完整步骤：
| 步骤 | 读入 | 栈（栈底→栈顶） | 输出 |
|---|---|---|---|
| 1 | A | A | |
| 2 | * | * | A |
| 3 | B | * | A B |
| 4 | + | + | A B * |
| 5 | C | + | A B * C |
| 6 | / | +/ | A B * C |
| 7 | D | +/ | A B * C D |
| 8 | - | - | A B * C D / + |
| 9 | E | - | A B * C D / + E |
| 结束 | A B * C D / + E - |
后缀表达式：
验证：按后缀表达式求值
- ✓
方法反思：
- 遇到
+时，栈顶是*（优先级更高），所以先弹出* - 遇到
-时，栈顶是/（优先级更高），先弹出/，再弹出+（同级也要弹出） - 同级运算符的处理：左结合的运算符遇到同级时要先弹出栈顶
例题2（中等）
题目：已知后缀表达式为 3 4 + 5 × 6 -，写出求值过程并给出最终结果。然后说明如果使用栈来实现后缀表达式求值，为什么必须"先弹出的是右操作数"。
命题意图：考查后缀表达式求值的操作过程，以及对栈在表达式求值中关键作用的深入理解。
审题分析：
- 已知：后缀表达式
3 4 + 5 × 6 - - 求解：求值过程和最终结果；解释为什么先弹出的是右操作数
解题思路： 按后缀求值算法逐步执行，并对减法和除法的非交换性进行分析。
完整步骤：
求值过程：
| 步骤 | 读入 | 操作 | 栈 |
|---|---|---|---|
| 1 | 3 | 入栈 | [3] |
| 2 | 4 | 入栈 | [3, 4] |
| 3 | + | 弹出4和3，计算3+4=7，入栈 | [7] |
| 4 | 5 | 入栈 | [7, 5] |
| 5 | × | 弹出5和7，计算7×5=35，入栈 | [35] |
| 6 | 6 | 入栈 | [35, 6] |
| 7 | - | 弹出6和35，计算35-6=29，入栈 | [29] |
最终结果：29
为什么先弹出的是右操作数？
考虑后缀表达式 a b -，它对应中缀表达式 。
栈中状态：[a, b]（a先入栈在底，b后入栈在顶）
- 第一次 Pop 得到 b（栈顶）
- 第二次 Pop 得到 a（栈底）
如果我们要计算 ，则：
- 第一次弹出的 b 是右操作数
- 第二次弹出的 a 是左操作数
- 计算
同理，对于 a b /（对应 ）：
- 第一次弹出 b（右操作数），第二次弹出 a（左操作数）
- 计算
结论：对于非交换运算（减法和除法），必须正确区分左操作数和右操作数。栈的后进先出特性决定了先弹出的是后入栈的，即后缀表达式中靠后的操作数，也就是右操作数。
方法反思：
- 后缀表达式求值的关键：记住"先出为右，后出为左"
- 对于加法和乘法（交换律成立），左右顺序不影响结果；但对于减法和除法，顺序至关重要
- 此理解对于正确实现求值算法至关重要，408大题中可能要求分析此过程
五、考情分析
| 分析维度 | 内容 |
|---|---|
| 考查频次 | 中缀转后缀、后缀表达式求值近5年出现3次以上，括号匹配和递归的栈模拟也有出现 |
| 常见题型 | 选择题（判断后缀表达式、括号匹配过程）、大题（表达式求值完整过程、递归转非递归） |
| 分值占比 | 大题可达8–12分（完整的中缀转后缀+求值过程） |
| 命题趋势 | 表达式求值一直是大题高频考点，趋势是要求更完整的过程展示和更复杂的应用场景 |
注：以上频次基于大纲权重与通用命题规律推测，待真题分析后校准。
六、易错点提醒
易错点1
- 错误表现：中缀转后缀时，同级运算符的处理出错（如
a - b + c转换错误） - 错误原因：不清楚同级运算符是否也需要弹出
- 正确做法：同级运算符也要弹出（左结合性），即当前运算符优先级 ≤ 栈顶优先级时都弹出。
a - b + c的后缀为a b - c +，不是a b c + -
易错点2
- 错误表现：后缀表达式求值时，减法和除法的操作数顺序搞反
- 错误原因：忘记"先弹出的是右操作数"，导致 算成了
- 正确做法：始终记住——
operand2 = Pop()（右操作数），operand1 = Pop()（左操作数），结果 =operand1 op operand2
易错点3
- 错误表现：括号匹配时只检查括号数量不检查类型，如
([)]被误判为匹配 - 错误原因：只数左右括号个数是否相等，没有检查类型对应关系
- 正确做法：每次右括号出栈时，必须检查栈顶左括号是否与之类型一致（
(配)，[配]，{配}）
易错点4
- 错误表现：递归转非递归时忘记保存局部变量或返回地址
- 错误原因：对系统调用栈的机制理解不透彻
- 正确做法：显式栈中必须保存递归函数的所有状态信息：参数、局部变量、当前执行到哪一步（通常用状态编号表示）
七、来源标注
- 依据2026考研统考大纲（408计算机学科专业基础综合）
- 依据《数据结构（C语言版）》严蔚敏版
- 依据《数据结构》王道考研辅导讲义