3.3.2 栈在表达式求值中的应用

教材导航 · 第3章

原书定位

印刷页P90起,对应PDF第102页。下文为目视整理的知识提要;完整内容见原书对照。

中缀表示符合书写习惯;前缀和后缀表示把运算顺序编码进排列,无须括号。表达式树的先序、后序分别对应前缀、后缀表达式。

中缀转后缀:操作数直接输出;左括号入栈;右括号使运算符弹出到对应左括号;普通左结合运算符到来时弹出优先级不低于它的栈顶运算符,再将当前运算符入栈。结束时弹出剩余运算符。若出现右结合运算符,须调整同优先级的规则。

后缀求值从左向右:操作数入栈;遇二元运算符,先弹出右操作数,再弹出左操作数,计算后压回。减法、除法尤其不能颠倒操作数。最大栈深度是模拟过程中同时存在的最大元素数,决定所需容量。

图3.15 表达式与表达式树

图3.15 表达式与表达式树,原书P90。

表3.1 中缀表达式转后缀表达式

表3.1 中缀表达式转后缀表达式,原书P91。

表3.2 后缀表达式求值

表3.2 后缀表达式求值,原书P92。

对应练习

3.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P90,PDF第102页

原书对照,原书P91,PDF第103页

原书对照,原书P92,PDF第104页