逆波兰表达式:中缀表达式转后缀表达式

2017-04-20 12:25 阅读 555 次 评论 0 条

逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。

逆多兰表达式

逆多兰表达式对于stack栈的运用是比较经典的,我们表述一个算式通常是:X+Y,即:操作数1  操作符 操作数2,当然也有特别的,比如"sqrt(N)",sqrt是操作符,N是操作数。而逆多兰表达式是:操作数1 操作数2 操作符。下图可以很清晰的表明这层关系。

后缀表达式在栈中的演变过程

下面这幅图是一个很好的说明,当我们遇到数字的时候,让其压栈,遇到操作符的时候,将栈顶的两个元素出栈,计算后的结果再压栈,直到栈中仅有一个元素时,出栈,剩下的这个元素就是运算结果。

基本+-*/的源代码

优先级四则运算

各类操作符的栈内外优先级如下表:

运算规则:

A)操作符栈初始化,将结束符#进栈,然后读取中缀表达式中的首字符ch(可省略)

B)重复执行以下步骤,直到ch='#',同时栈顶的操作符也是‘#’时,循环终止(可省略)

1> 若ch是操作数则直接输出,读取下一个字符

2> 若ch是操作符,判断ch的优先级icp和当前位于栈顶的操作符op的优先级isp

1> 若icp(ch) > isp(op),令ch进栈,读入下一个字符ch

2> 若icp(ch) < isp(op),退栈并输出

3> 若icp(ch) == isp(op),退栈但不输出,若退出的是‘(’继续读入下一个字符ch

C)算法结束,输出的序列即为后缀表达式

优先级的四则运算源代码

无论是前缀表达式、中缀表达式还是后缀表达式,都是对栈的一个扩展与运用,熟悉表达式之间的变换对栈的理解是非常有帮助的。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:逆波兰表达式:中缀表达式转后缀表达式 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情