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

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

摘要

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

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