考点频率★★★★★栈的核心应用选择题必考下午题偶尔结合考查难度⭐⭐⭐⭐建议重点掌握中缀转后缀的规则、后缀表达式的手工计算方法这是下午题的隐性考点1️⃣ 为什么需要后缀表达式你平时写的算式是(3 4) × 5 - 6这叫中缀表达式——运算符在操作数中间。人看得很舒服但计算机处理起来很麻烦因为要考虑括号和运算符优先级。为了让计算机更方便计算人们设计了两种替代格式后缀表达式逆波兰表达式运算符在操作数后面。例如3 4 5 × 6 -前缀表达式波兰表达式运算符在操作数前面。例如- × 3 4 5 6后缀表达式的最大优点不需要括号不需要考虑优先级按顺序扫描即可计算。2️⃣ 中缀表达式 → 后缀表达式手工转换方法2.1 方法一加括号法适合手工计算操作步骤按运算符优先级给表达式加括号每个运算符对应一对括号将每个运算符移到它对应的右括号后面去掉所有括号示例将(3 4) × 5 - 6转为后缀表达式第1步加括号 ((3 4) × 5) - 6 ↓ 每个运算符对应一对括号 ((3 4) × 5) - 6 → (((3 4) × 5) - 6) 最内层3 4 → (3 4 ) 再外层× 5 → ((3 4 ) 5 ×) 最外层- 6 → (((3 4 ) 5 ×) 6 -) 第2步去掉括号 → 3 4 5 × 6 -2.2 方法二符号栈法理解计算机是怎么做的中缀转后缀计算机实现遍历中缀表达式的每个 token操作数或运算符按规则处理操作数直接输出到后缀表达式左括号(直接入栈右括号)不断弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出运算符当栈顶运算符的优先级 ≥ 当前运算符优先级时弹出并输出栈顶然后将当前运算符入栈示例3 4 × 5 - 6步骤符号输出后缀运算符栈说明133操作数直接输出23栈空直接入栈343 4操作数直接输出4×3 4 ×栈顶优先级低于×直接入栈553 4 5 ×操作数直接输出6-3 4 5 ××优先级 ≥-弹出×优先级 ≥-弹出然后-入栈763 4 5 × 6-操作数直接输出8结束3 4 5 × 6 -弹出栈中剩余运算符结果3 4 5 × 6 -3️⃣ 后缀表达式的计算计算规则从左到右扫描后缀表达式遇到操作数入栈遇到运算符弹出栈顶的两个操作数计算结果后入栈扫描结束后栈顶就是最终结果示例计算3 4 5 × 6 -步骤扫描到操作栈13入栈[3]24入栈[3, 4]35入栈[3, 4, 5]4×弹出 4 和 5 → 4×520 → 入栈[3, 20]56入栈[3, 20, 6]6-弹出 20 和 6 → 20-614 → 入栈[3, 14]7结束弹出栈顶14结果14与原中缀表达式(34)×5-635-629不一致等等这里有问题⚠️发现错误上面的计算结果是 14但原式(34)×5-6应该等于 29。原因我把运算符优先级搞反了。3 4 × 5 - 6正确的后缀是3 4 5 × 6 -而不是3 4 5 × 6 -。修正后的计算步骤扫描到栈13[3]24[3, 4]35[3, 4, 5]4×[3, 20]5[23]66[23, 6]7-[17]结果17仍然不对等等原式34×5-6按乘除优先是320-617正确我本来想写的是(34)×5-6但写成34×5-6了。所以(34)×5-6对应的后缀是3 4 5 × 6 -计算如下步骤栈3[3]4[3, 4][7]5[7, 5]×[35]6[35, 6]-[29]结果29 ✅4️⃣ 中缀 → 后缀 → 求值完整例题题目计算中缀表达式8 (3 - 1) × 2第1步中缀 → 后缀加括号法8 ((3 - 1) × 2)→(8 ((3 1 -) 2 ×) )→ 去掉括号8 3 1 - 2 × 第2步计算后缀8 3 1 - 2 × 步骤扫描到栈18[8]23[8, 3]31[8, 3, 1]4-[8, 2]52[8, 2, 2]6×[8, 4]7[12]结果12 ✅5️⃣ 运算符优先级速查运算符优先级( )最高用于改变运算顺序×/高-低6️⃣ 经典例题例题1中缀转后缀中缀表达式a b * c - d / e对应的后缀表达式是 。A.a b c * d e / -B.a b c * d e / - C.a b * c d e / -D.a b c * d e - /解析a b × c - d / e→a (b c ×) (d e /) -→a b c × d e / -。选A。例题2后缀求值后缀表达式5 1 2 4 × 3 -的值为 。解析步骤栈5[5]1[5, 1]2[5, 1, 2][5, 3]4[5, 3, 4]×[5, 12][17]3[17, 3]-[14]答案147️⃣ 记忆口诀中缀转后缀操作数直接写。左括号入栈右括号弹到底。运算符看栈顶同级高先弹。后缀求值用栈数字入栈运算符弹两数。8️⃣ 小测验评论区对答案中缀表达式(a b) * (c - d)对应的后缀表达式是 。A.a b c d - *B.a b c d - *C.a b c - d *D.a b c d - *答案下期公布。本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #栈 #后缀表达式 #表达式求值 #数据结构 #软考备考 【数据结构】栈的应用：表达式求值（后缀表达式）
考点频率★★★★★栈的核心应用选择题必考下午题偶尔结合考查难度⭐⭐⭐⭐建议重点掌握中缀转后缀的规则、后缀表达式的手工计算方法这是下午题的隐性考点1️⃣ 为什么需要后缀表达式你平时写的算式是(3 4) × 5 - 6这叫中缀表达式——运算符在操作数中间。人看得很舒服但计算机处理起来很麻烦因为要考虑括号和运算符优先级。为了让计算机更方便计算人们设计了两种替代格式后缀表达式逆波兰表达式运算符在操作数后面。例如3 4 5 × 6 -前缀表达式波兰表达式运算符在操作数前面。例如- × 3 4 5 6后缀表达式的最大优点不需要括号不需要考虑优先级按顺序扫描即可计算。2️⃣ 中缀表达式 → 后缀表达式手工转换方法2.1 方法一加括号法适合手工计算操作步骤按运算符优先级给表达式加括号每个运算符对应一对括号将每个运算符移到它对应的右括号后面去掉所有括号示例将(3 4) × 5 - 6转为后缀表达式第1步加括号 ((3 4) × 5) - 6 ↓ 每个运算符对应一对括号 ((3 4) × 5) - 6 → (((3 4) × 5) - 6) 最内层3 4 → (3 4 ) 再外层× 5 → ((3 4 ) 5 ×) 最外层- 6 → (((3 4 ) 5 ×) 6 -) 第2步去掉括号 → 3 4 5 × 6 -2.2 方法二符号栈法理解计算机是怎么做的中缀转后缀计算机实现遍历中缀表达式的每个 token操作数或运算符按规则处理操作数直接输出到后缀表达式左括号(直接入栈右括号)不断弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出运算符当栈顶运算符的优先级 ≥ 当前运算符优先级时弹出并输出栈顶然后将当前运算符入栈示例3 4 × 5 - 6步骤符号输出后缀运算符栈说明133操作数直接输出23栈空直接入栈343 4操作数直接输出4×3 4 ×栈顶优先级低于×直接入栈553 4 5 ×操作数直接输出6-3 4 5 ××优先级 ≥-弹出×优先级 ≥-弹出然后-入栈763 4 5 × 6-操作数直接输出8结束3 4 5 × 6 -弹出栈中剩余运算符结果3 4 5 × 6 -3️⃣ 后缀表达式的计算计算规则从左到右扫描后缀表达式遇到操作数入栈遇到运算符弹出栈顶的两个操作数计算结果后入栈扫描结束后栈顶就是最终结果示例计算3 4 5 × 6 -步骤扫描到操作栈13入栈[3]24入栈[3, 4]35入栈[3, 4, 5]4×弹出 4 和 5 → 4×520 → 入栈[3, 20]56入栈[3, 20, 6]6-弹出 20 和 6 → 20-614 → 入栈[3, 14]7结束弹出栈顶14结果14与原中缀表达式(34)×5-635-629不一致等等这里有问题⚠️发现错误上面的计算结果是 14但原式(34)×5-6应该等于 29。原因我把运算符优先级搞反了。3 4 × 5 - 6正确的后缀是3 4 5 × 6 -而不是3 4 5 × 6 -。修正后的计算步骤扫描到栈13[3]24[3, 4]35[3, 4, 5]4×[3, 20]5[23]66[23, 6]7-[17]结果17仍然不对等等原式34×5-6按乘除优先是320-617正确我本来想写的是(34)×5-6但写成34×5-6了。所以(34)×5-6对应的后缀是3 4 5 × 6 -计算如下步骤栈3[3]4[3, 4][7]5[7, 5]×[35]6[35, 6]-[29]结果29 ✅4️⃣ 中缀 → 后缀 → 求值完整例题题目计算中缀表达式8 (3 - 1) × 2第1步中缀 → 后缀加括号法8 ((3 - 1) × 2)→(8 ((3 1 -) 2 ×) )→ 去掉括号8 3 1 - 2 × 第2步计算后缀8 3 1 - 2 × 步骤扫描到栈18[8]23[8, 3]31[8, 3, 1]4-[8, 2]52[8, 2, 2]6×[8, 4]7[12]结果12 ✅5️⃣ 运算符优先级速查运算符优先级( )最高用于改变运算顺序×/高-低6️⃣ 经典例题例题1中缀转后缀中缀表达式a b * c - d / e对应的后缀表达式是 。A.a b c * d e / -B.a b c * d e / - C.a b * c d e / -D.a b c * d e - /解析a b × c - d / e→a (b c ×) (d e /) -→a b c × d e / -。选A。例题2后缀求值后缀表达式5 1 2 4 × 3 -的值为 。解析步骤栈5[5]1[5, 1]2[5, 1, 2][5, 3]4[5, 3, 4]×[5, 12][17]3[17, 3]-[14]答案147️⃣ 记忆口诀中缀转后缀操作数直接写。左括号入栈右括号弹到底。运算符看栈顶同级高先弹。后缀求值用栈数字入栈运算符弹两数。8️⃣ 小测验评论区对答案中缀表达式(a b) * (c - d)对应的后缀表达式是 。A.a b c d - *B.a b c d - *C.a b c - d *D.a b c d - *答案下期公布。本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #栈 #后缀表达式 #表达式求值 #数据结构 #软考备考