【2】7 栈的应用_表达式求值 理论
目录
1. 中缀表达式
算数表达式中由三部分组成: 操作数、运算符(加减乘除)、界限符(括号)。
界限符是必不可少的,反映了计算的先后顺序。
可以不通过界限符也能无歧义地表达运算顺序吗?(波兰数学家)
===> 逆波兰表达式 = 后缀表达式, 波兰表达式 = 前缀表达式。
操作数的相对顺序不能变!
运算符生效的先后顺序是一一对应的。
2. 中缀表达式转后缀表达式
如果要用计算机实现一个中缀转后缀算法的话,输入同一个中缀表达式,我们只应该得到一种结果。(算法有一个必须具备的特性——确定性,即同样的输入只能得到同样的输出 )
所以尽管上面手算的两种结果都是正确的,但是用计算机实现这个算法得到的结果是左边这种结果。所以考试时验证算法是是否正确应该用左边的式子验证而不是右边的!
“左优先原则”:只要左边的运算符能先计算,就优先计算左边的! 保证手算和机算结果相同!
比如上式中,左边的 - 法可以先生效,右边的 / 法也可以先生效,由左优先原则,应该先做 - 法。
答题时,不要用左优先原则直接作答,因为这是个人理解总结,书上并没有定义。
3. 后缀表达式的计算
操作数的顺序不能错 !!!!!
4. 中缀表达式转前缀表达式
5. 前缀表达式的计算