当前位置：首页 > backend >正文

栈的应用:表达式求值

backend 2025/6/29 8:23:04

一、核心问题：表达式求值的难点

对于像 3*(7-2)# 这样的表达式，直接计算会面临 “运算顺序” 的问题：

先算括号里的 7-2，还是先算乘法？
如何处理运算符的优先级（乘除高于加减）？
如何匹配括号（括号内的要优先计算）？

栈的作用就是 “管理运算顺序”：

用两个栈：
- OPND 栈：存操作数（如 3、7、2 ）和中间结果（如 5、15 ）。
- OPTR 栈：存运算符（如 *、(、- ）和边界符（如 # ）。
通过 “比较运算符优先级”，决定是 “压栈等待” 还是 “弹出计算”。

二、关键规则：算符优先关系表

这张表是 “指挥中心”，决定运算符的优先级：

表格里的 θ₁ 是 栈顶运算符，θ₂ 是 当前扫描到的运算符。
比较结果：
- <：当前运算符优先级更高 → 压入 OPTR 栈，等待后续计算。
- >：栈顶运算符优先级更高 → 弹出栈顶运算符，从 OPND 取数计算。
- =：括号匹配（如 ( 和 ) 相遇），弹出栈顶的 (，继续扫描。

举个简单例子：

栈顶是 +（θ₁），当前运算符是 *（θ₂）：查表格，+ 和 * 的交叉是 < → * 优先级更高，* 压栈。
栈顶是 *（θ₁），当前运算符是 +（θ₂）：查表格，* 和 + 的交叉是 > → * 优先级更高，先弹出 * 计算。

三、算法步骤（结合图片里的流程）

以 3*(7-2)# 为例，完整走一遍流程：

1. 初始化

OPTR 栈压入 #（作为表达式的 “起始边界符”）。
OPND 栈为空。
扫描指针指向表达式第一个字符 '3'。

2. 循环处理（直到扫描到 `#` 且栈顶也是 `#`）

核心逻辑：

遇到 操作数（如 3、7、2 ）→ 压入 OPND 栈。
遇到 运算符（如 *、(、- ）→ 查 “优先关系表”，决定是 “压栈” 还是 “计算”。

逐步演示：

步骤	扫描字符 `ch`	操作	说明
1	`'3'`	压入 `OPND` 栈	`OPND: [3]`，`OPTR: [#]`
2	`'*'`	比较 `OPTR` 栈顶 `#` 和 `*` → `<`	`` 压入 `OPTR` 栈 → `OPTR: [#, ]`
3	`'('`	比较 `OPTR` 栈顶 `*` 和 `(` → `<`	`(` 压入 `OPTR` 栈 → `OPTR: [#, *, (]`
4	`'7'`	压入 `OPND` 栈	`OPND: [3, 7]`
5	`'-'`	比较 `OPTR` 栈顶 `(` 和 `-` → `<`	`-` 压入 `OPTR` 栈 → `OPTR: [#, *, (, -]`
6	`'2'`	压入 `OPND` 栈	`OPND: [3, 7, 2]`
7	`')'`	比较 `OPTR` 栈顶 `-` 和 `)` → `>`	弹出 `-`，计算 `7-2=5`，结果压入 `OPND` → `OPND: [3, 5]`；然后比较栈顶 `(` 和 `)` → `=`，弹出 `(`
8	`'#'`	比较 `OPTR` 栈顶 `*` 和 `#` → `>`	弹出 ``，计算 `35=15`，结果压入 `OPND` → `OPND: [15]`
9	`'#'`	扫描结束，返回 `OPND` 栈顶	结果 `15`

3. 终止条件

当扫描到 #，且 OPTR 栈顶也是 # 时，循环结束，OPND 栈顶就是最终结果。

四、代码逻辑解析（结合图片里的函数）

以下是核心函数的逻辑拆解（对应图片里的 EvaluateExpression 函数）：

1. 初始化栈

InitStack(OPTR); Push(OPTR, '#'); // OPTR 栈初始化，压入 #
InitStack(OPND); ch = getchar();  // OPND 栈初始化，读第一个字符

2. 循环处理表达式

while (ch != '#' || GetTop(OPTR) != '#') { // 没扫描完或栈顶不是 #if (!In(ch)) { // ch 不是运算符 → 压入 OPNDPush(OPND, ch); ch = getchar(); } else { // ch 是运算符 → 比较优先级switch (Precede(GetTop(OPTR), ch)) { case '<': // 当前运算符优先级高 → 压栈Push(OPTR, ch); ch = getchar(); break;case '>': // 栈顶运算符优先级高 → 弹出计算Pop(OPTR, theta); // 弹出运算符Pop(OPND, b); Pop(OPND, a); // 弹出两个操作数Push(OPND, Operate(a, theta, b)); // 计算后压入结果break;case '=': // 括号匹配 → 弹出 (，继续扫描Pop(OPTR, x); ch = getchar(); break;}}
}

3. 返回结果

return GetTop(OPND); // OPND 栈顶就是结果

五、关键函数说明

In(ch)：判断 ch 是否是运算符（+、-、*、/、(、)、# ）。
Precede(θ₁, θ₂)：查 “优先关系表”，返回 <、> 或 =。
Operate(a, theta, b)：执行运算（如 a + b、a * b ），注意顺序（a 是栈底的数，b 是栈顶的数，比如 7-2 中 a=7，b=2 ）。