Appearance
表达式求值
为什么需要表达式求值
我们日常书写的算术表达式如 (3 + 4) * 5 是中缀表达式——运算符位于操作数中间。这种写法对人类直观，但对计算机并不友好：运算符有优先级，还有括号改变求值顺序，直接解析非常麻烦。
编译器和计算器的做法是：先将中缀表达式转换为后缀表达式（也叫逆波兰表达式），再对后缀表达式求值。这两个步骤都依赖栈，是 408 考研中栈的经典应用。
核心思想
三种表达式的区别在于运算符相对操作数的位置：
| 类型 | 写法 | 示例（中缀 a + b * c） |
|---|---|---|
| 中缀表达式 | 运算符在操作数中间 | a + b * c |
| 前缀表达式（波兰式） | 运算符在操作数前面 | + a * b c |
| 后缀表达式（逆波兰式） | 运算符在操作数后面 | a b c * + |
核心要点：
- 后缀表达式不需要括号，运算顺序由运算符出现的先后唯一确定
- 中缀转后缀：使用一个运算符栈，按优先级规则决定何时弹出运算符
- 后缀求值：使用一个操作数栈，遇到运算符就弹出栈顶两个操作数计算
运算符优先级（栈外/栈内）：
| 运算符 | 栈外优先级（isp） | 栈内优先级（icp） |
|---|---|---|
( | 最高 | 最低 |
* / | 高 | 高 |
+ - | 低 | 低 |
) | 最低 | — |
左括号
(入栈前优先级最高（保证能入栈），入栈后优先级最低（不会被普通运算符弹出，只有)才能将它弹出）。
交互可视化
通过下方的交互动画，你可以逐步观察表达式求值的执行过程：
操作详解
中缀转后缀
算法思路：从左到右扫描中缀表达式，借助一个运算符栈，将运算符按正确的顺序输出到后缀表达式。
关键步骤：
- 遇到操作数：直接输出到后缀表达式
- 遇到
(：直接入栈 - 遇到
)：依次弹出栈顶运算符并输出，直到遇到(，将(弹出但不输出 - 遇到运算符：将栈中优先级 ≥ 当前运算符的运算符依次弹出并输出，然后当前运算符入栈
- 扫描结束后，将栈中剩余运算符依次弹出并输出
手算示例：将 a + b * c - (d / e) 转换为后缀表达式
| 扫描元素 | 动作 | 运算符栈 | 后缀输出 |
|---|---|---|---|
a | 输出 | 空 | a |
+ | 入栈 | + | a |
b | 输出 | + | a b |
* | 入栈（优先级高于 +） | + * | a b |
c | 输出 | + * | a b c |
- | 弹出 *、+，入栈 | - | a b c * + |
( | 入栈 | - ( | a b c * + |
d | 输出 | - ( | a b c * + d |
/ | 入栈 | - ( / | a b c * + d |
e | 输出 | - ( / | a b c * + d e |
) | 弹出 /，弹出 ( | - | a b c * + d e / |
| 结束 | 弹出 - | 空 | a b c * + d e / - |
参考代码（C）：
c
// 中缀表达式转后缀表达式
// infix: 输入的中缀表达式字符串
// postfix: 输出的后缀表达式字符串
void infixToPostfix(char* infix, char* postfix) {
char stack[MAX_SIZE]; // 运算符栈
int top = -1;
int j = 0; // postfix 的写入位置
for (int i = 0; infix[i] != '\0'; i++) {
char ch = infix[i];
if (isOperand(ch)) {
// 操作数直接输出
postfix[j++] = ch;
} else if (ch == '(') {
// 左括号直接入栈
stack[++top] = ch;
} else if (ch == ')') {
// 右括号：弹出直到遇到左括号
while (top >= 0 && stack[top] != '(')
postfix[j++] = stack[top--];
top--; // 弹出左括号
} else {
// 普通运算符：弹出优先级 >= 当前运算符的栈顶元素
while (top >= 0 && stack[top] != '(' &&
priority(stack[top]) >= priority(ch))
postfix[j++] = stack[top--];
stack[++top] = ch;
}
}
// 弹出栈中剩余运算符
while (top >= 0)
postfix[j++] = stack[top--];
postfix[j] = '\0';
}
int priority(char op) {
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}后缀表达式求值
算法思路：从左到右扫描后缀表达式，使用一个操作数栈存放中间结果。
关键步骤：
- 遇到操作数：压入操作数栈
- 遇到运算符：弹出栈顶两个操作数，先弹出的是右操作数，后弹出的是左操作数，计算结果压回栈
- 扫描结束后，栈顶即为最终结果
手算示例：求值 3 4 2 * + 5 -
| 扫描元素 | 动作 | 操作数栈 |
|---|---|---|
3 | 入栈 | 3 |
4 | 入栈 | 3 4 |
2 | 入栈 | 3 4 2 |
* | 弹出 2、4，计算 4*2=8，入栈 | 3 8 |
+ | 弹出 8、3，计算 3+8=11，入栈 | 11 |
5 | 入栈 | 11 5 |
- | 弹出 5、11，计算 11-5=6，入栈 | 6 |
最终结果为 6。
注意弹出顺序：先弹出的是右操作数，后弹出的是左操作数。对于
-和/这类不满足交换律的运算符，顺序不能搞反，这是常见错误点。
参考代码（C）：
c
// 后缀表达式求值
// postfix: 后缀表达式字符串（操作数为单个数字字符）
int evalPostfix(char* postfix) {
int stack[MAX_SIZE]; // 操作数栈
int top = -1;
for (int i = 0; postfix[i] != '\0'; i++) {
char ch = postfix[i];
if (isdigit(ch)) {
// 操作数入栈
stack[++top] = ch - '0';
} else {
// 弹出两个操作数，注意顺序
int right = stack[top--];
int left = stack[top--];
int result;
switch (ch) {
case '+': result = left + right; break;
case '-': result = left - right; break;
case '*': result = left * right; break;
case '/': result = left / right; break;
}
stack[++top] = result;
}
}
return stack[top];
}复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 中缀转后缀 | O(n) | 每个字符最多入栈、出栈各一次 |
| 后缀表达式求值 | O(n) | 单次扫描，每个元素操作 O(1) |
| 中缀直接求值 | O(n) | 需要两个栈（运算符栈 + 操作数栈） |
空间复杂度：O(n)，栈的最大深度与表达式长度成正比。
考研高频考点
- ⭐ 给定中缀表达式，手算转换为后缀/前缀表达式（选择题/填空题高频）
- ⭐ 给定后缀表达式，手算求值过程及结果（选择题高频）
- ⭐ 中缀转后缀过程中运算符栈的变化（选择题/简答题）
- ⭐ 操作数弹出顺序（左/右操作数）——除法和减法的易错点
- 前缀表达式的求值方法（从右到左扫描，其余与后缀类似）
- 中缀表达式直接求值的双栈算法（偶尔考）
- 括号匹配与表达式合法性判断（栈的另一经典应用，常结合考察）