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

从中缀表达式说起

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

          3+5x4

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

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

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

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

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

后缀表达式

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

• 3+5x4：3 5 4 x +
• (3+5)x4：3 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。

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

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

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 - 为例，我们来看看求值过程：

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

总结

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

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

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

扩散思考

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

参考资料

• 逆波兰表达式
• 调度场算法
• 编译原理-词法分析