🏷️ 知识点：后序表达式求值
2018 年第 1 题
数据结构
选择题
若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作：
① 从 S1 中依次弹出两个操作数 a 和 b；② 从 S2 中弹出一个运算符 op；③ 执行相应的运算 b op a；④ 将运算结果压入 S1。
假定 S1 中的操作数依次是 5,8,3,2（2 在栈顶），S2 中的运算符依次是 ×,−,+ （ + 在栈顶）。调用 3 次 F() 后，S1 栈顶保存的值是（ ）。
A. -15 B. 15 C. -20 D. 20
[tag_link]
正确答案：B
本题考察 后序表达式求值，调用三次 F() 栈中内容如下表所示：
| 调用次数 | S1 初始状态（栈底 → 栈顶） | S2 初始状态（栈底 → 栈顶） | 弹出操作数 a, b | 弹出运算符 op | 执行运算 b op a | 运算结果入栈后 S1 状态（栈底 → 栈顶） |
|---|---|---|---|---|---|---|
| 第一次 | 5, 8, 3, 2 | ×, −, + | a=2, b=3 | + | 3 + 2 = 5 | 5, 8, 5 |
| 第二次 | 5, 8, 5 | ×, − | a=5, b=8 | − | 8 − 5 = 3 | 5, 3 |
| 第三次 | 5, 3 | × | a=3, b=5 | × | 5 × 3 = 15 | 15 |
调用三次 F() 后，S1 的栈顶是 15，因此选择 B。