逆波兰式(Reverse
Polish Notation,RPN,或逆波兰记法),也叫后缀表达式(将
运算符写在
操作数之后)。
算法定义
(1)如果E是一个变量或常量,则E的
后缀式是E本身。
(2)如果E是E1 op E2形式的表达式,这里op是任何二元
操作符,则E的后缀式为E1'E2' op,这里E1'和E2'分别为E1和E2的后缀式。
(3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。
如:我们平时写a+b,这是
中缀表达式,写成后缀表达式就是:ab+
(a+b)*c-(a+b)/e的后缀表达式为:
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
算法作用
实现逆波兰式的算法,难度并不大,但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的
思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。
算法实现
将一个普通的中缀表达式转换为
逆波兰表达式的一般算法是:
首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为存放结果(逆波兰式)的栈S2(空栈),S1栈可先放入
优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定非#不可。从中缀式的左端开始取字符,逐序进行如下步骤:
(1)若取出的字符是
操作数,则分析出完整的运算数,该操作数直接送入S2栈。
(2)若取出的字符是运算符,则将该运算符与S1栈栈顶元素比较,如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符(包括左括号)优先级,则将该运算符进S1栈,否则,将S1栈的栈顶运算符弹出,送入S2栈中,直至S1栈栈顶运算符(包括左括号)低于(不包括等于)该
运算符优先级时停止弹出运算符,最后将该运算符送入S1栈。
(3)若取出的字符是“(”,则直接送入S1栈顶。
(4)若取出的字符是“)”,则将距离S1栈栈顶最近的“(”之间的运算符,逐个出栈,依次送入S2栈,此时抛弃“(”。
(5)重复上面的1~4步,直至处理完所有的
输入字符。
(6)若取出的字符是“#”,则将S1栈内所有运算符(不包括“#”),逐个出栈,依次送入S2栈。
完成以上步骤,S2栈便为逆波兰式输出结果。不过S2应做一下
逆序处理。便可以按照逆波兰式的计算方法计算了!
计算方法
新建一个
表达式,如果当前字符为变量或者为数字,则压栈,如果是运算符,则将
栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
算法举例
下面以(a+b)*c为例子进行说明:
(a+b)*c的逆波兰式为ab+c*,假设计算机把ab+c*按从左到右的顺序压入栈中,并且按照遇到
运算符就把
栈顶两个元素出栈,执行运算,得到的结果再入栈的原则来进行处理,那么ab+c*的执行结果如下:
(1)a入栈(0位置)
(2)b入栈(1位置)
(3)遇到运算符“+”,将a和b出栈,执行a+b的操作,得到结果d=a+b,再将d入栈(0位置)
(4)c入栈(1位置)
(5)遇到运算符“*”,将d和c出栈,执行d*c的操作,得到结果e,再将e入栈(0位置)
经过以上运算,计算机就可以得到(a+b)*c的运算结果e了。
逆波兰式除了可以实现上述类型的运算,它还可以派生出许多新的算法,
数据结构,这就需要灵活运用了。逆波兰式只是一种序列体现形式。
算法图示
其中△代表一个标识,ω代表
预算法,名字Q代表变量(如int a,b等),
算法用到三个栈:a栈,b栈,in栈。
其中a栈用来存储逆波兰式,b用来存储△号和
运算符,in栈为输入栈。
pop(in)为输入栈栈顶元素出栈,pop(a,Q)为Q入a栈,NEXT算法即为进行下一轮循环,其中ω1
算法开始时,现将△如b栈,输入栈以#号结尾。
程序实现
数据结构版
还有一种方法,用二叉树。
二叉树法
将最终进行的运算符记为
根节点,将两边的
表达式分别记为左右
子树,依次进行直到所有的运算符与数字或字母标在一棵
二叉树上。然后对二叉树进行
后序遍历即可。