后缀表达式之逆波兰表示法

HackerPie
·

从中缀表达式说起

对于人类来说,中缀表达式是最直观自然的,比如“3+5x4”或者“(3+5)x4”,一般来说,对于中缀表达式,在程序中会用一个抽象语法树来表示表达式和求值,比如:

          3+5x4

            +
           / \
          /   \
         3     x
              / \
             /   \
            5     4
--------------------------------
        (3+5)x4

               x
              / \
             /   \
            +     4
           / \
          /   \
         3     5

后续表达式求值使用二叉树的中序遍历便可。

但是这种表达式对于计算机来说,会有2个可以考虑提升的问题:

  • 对于计算机不够直观,需要在树的结构上进行遍历和求值;
  • 额外的括号来用于明确运算优先级。

后缀表达式

后缀表达式,也叫逆波兰表达式,前述的表达式对应的后缀表达式为:

  • 3+5x43 5 4 x +
  • (3+5)x43 5 + 4 x

可以看出后缀表达式的特点:

  • 操作符在操作数的末尾,比如 5 x 4 表示为 5 4 x
  • 无需括号表达优先级

从计算机的角度,后缀表达式还有以下特点:

  • 由于没有括号,可以节省内存
  • 可以基于栈结构实现后缀表达式的求值
  • 如果对抽象语法树进行末序遍历,刚好可以得到逆波兰表达式,这点比较有意思

将中缀表达式转为后缀表达式

为了将中缀表达式转为后缀表达式,一般需要用到的是调度场算法,算法中需要用到一个输出队列和一个操作符栈,完整的算法细节比较多,这里简化为简单的四则运算(支持括号)来描述精简版算法,如果需要支持完整的运算符或者函数等,需要自行学习完整的调度场算法。

以下用伪代码描述(注意: 算法中的“单词符号”一词参考编译原理中的“token”一词,意思是一样的,我为了伪代码不会中英混杂,才写了中文名字,不一定精确):

声明 Q:输出队列
声明 S:操作符栈

遍历中缀表达式中的每一个单词符号 x:
    如果 x 是一个操作数,直接将 x 追加到输出队列 Q 末尾,否则往下检查;
    如果 x 是一个左括号“(”,将 x 压入操作符栈 S 栈顶,否则往下检查;
    如果 x 是一个操作符:
        如果操作符栈 S 栈顶为一个优先级大于等于 x 的操作符,则将 S 栈顶的运算符弹出并且追加到输出队列 Q 末尾,最后将 x 压入栈顶;
        如果操作符栈 S 栈顶为一个优先级小于 x 的操作符,或者不为操作符(在这个简化算法里,只有可能是左括号),则直接将 x 压入栈顶即可。
    如果 x 是一个右括号“)”,则将操作符栈 S 栈顶到往下第一个左括号“(”之间的元素依次弹出并且追加到输出队列末尾,将“(”出栈丢弃,x 也不用入栈。注意:如果栈到底后仍没有找到左括号,则说明表达式不合法,左右括号不匹配。
最后将栈 S 中的元素全部依次弹出并且入队列 Q。

实例演示

用一个稍微复杂的四则运算表达式来举例:(12+5)x(8-1)-6x6

则算法对应每一步的过程以及队列和栈的状态如下表所示:

遍历序号 单词符号 输出队列(左边为队首) 操作符栈(左侧为栈底) 解释说明
1 ( (空) ( 遇到左括号,直接入栈
2 12 12 ( 12 为操作数,直接入队列
3 + 12 (, + + 为操作符,栈顶此时为非操作符,直接入栈
4 5 12, 5 (, + 5 为操作数,直接入队列
5 ) 12, 5, + (空) ) 为右括号,需要将栈顶到第一个左括号之间的元素出栈入队列
6 x 12, 5, + x x 为操作符,栈顶为空,直接入栈
7 ( 12, 5, + x, ( 左括号直接入栈
8 8 12, 5, +, 8 x, ( 8 为操作数,直接入队列
9 - 12, 5, +, 8 x, (, - - 为操作符,栈顶为非操作符,直接入栈
10 1 12, 5, +, 8, 1 x, (, - 1 为操作数,直接入队列
11 ) 12, 5, +, 8, 1, - x 遇到右括号,需要将栈顶到第一个左括号之间的元素出栈入队列
12 - 12, 5, +, 8, 1, -, x - - 为操作符,此时栈顶元素也为操作符,且优先级更高,则将栈顶弹出入队列,再将 - 入栈
13 6 12, 5, +, 8, 1, -, x, 6 - 6 为操作数,直接入队列
14 x 12, 5, +, 8, 1, -, x, 6 -, x x 为操作符,此时栈顶元素也为操作符,但优先级较低,这个时候直接将 x 入栈即可
15 6 12, 5, +, 8, 1, -, x, 6, 6 -, x 6 为操作数,直接入队列

遍历结束后,操作符栈不为空,将栈里元素依次弹出并且追加到输出队列末尾,可得输出队列结果为:

12, 5, +, 8, 1, -, x, 6, 6, x, -

也就是得到的后缀表达式是 12 5 + 8 1 - x 6 6 x -

求值计算

后缀表达式的求值过程相对比较简单直观,同样需要借助栈来实现,以下为简要的四则运算对应的后缀表达式求值算法描述:

声明 S:求值栈

遍历后缀表达式中的每一个单词符号 x:
    如果 x 为操作数,则直接将 x 压入求值栈 S,否则往下继续;
    如果 x 为操作符(在这个例子中,只有可能是+-✖️÷之一),则从栈中弹出2个元素 a 和 b,将 b 和 a 执行对应操作符的运算,将运算结果压入栈。
最后栈中应该只有一个元素,即为表达式的最终结果。

以前一小节得到的后缀表达式 12 5 + 8 1 - x 6 6 x - 为例,我们来看看求值过程:

遍历序号 单词符号 求值栈(左侧为栈底) 解释说明
1 12 12 操作数直接入栈
2 5 12, 5 操作数直接入栈
3 + 17 遇到操作符,弹出栈中的 5 和 12,做加法 12 + 5,得到 17,压回栈中
4 8 17, 8 操作数直接入栈
5 1 17, 8, 1 操作数直接入栈
6 - 17, 7 遇到操作符,弹出栈中的 1 和 8,做减法 8 - 1,得到 7,压回栈中
7 x 119 遇到操作符,弹出栈中的 7 和 17,做乘法 17 x 7,得到 119,压回栈中
8 6 119, 6 操作数直接入栈
9 6 119, 6, 6 操作数直接入栈
10 x 119, 36 遇到操作符,弹出栈中的 6 和 6,做乘法 6 x 6,得到 36,压回栈中
11 - 83 遇到操作符,弹出栈中的 36 和 119,做乘法 119 - 36,得到 83,压回栈中

最后,栈里刚好只剩一个元素 83,即为我们的求值结果。

总结

逆波兰表达式是一种更适合计算机理解的表达式表示方法,相比较抽象语法树的形式:

  • 在表示上,它能够节省更多的内存(如果用树,一方面的内存开销在于括号节点,另一方面的内存开销在于树节点之间的指针,如果考虑到遍历,还会有递归调用带来的调用栈的内存开销);
  • 在求值上,逆波兰表达式也更简洁,同时可以避免树遍历过程中的递归形式,递归是一种人类阅读起来比较费脑的代码结构;
  • 支持无歧义的运算优先级而无需引入括号。

再次声明,本文中的调度场算法和求值算法均为简化模型,如果需要了解学习完整的算法,请自行查阅维基百科等,本文末尾附有参考资料链接。

扩散思考

  • 前缀表达式也应该具备类似的特点?
  • 既然是叫逆波兰表达式,那是不是也应该有波兰表达式?我猜就是前缀表达式?
  • 结合后缀表达式的求值算法,是不是可以快速得到将后缀表达式还原为中缀表达式的算法?

参考资料

评论
社区准则 博客 联系 反馈 状态
主题