一日一技：逆波兰式

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰结构由弗里德里希·鲍尔（Friedrich L. Bauer）和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林（Charles Hamblin）在1960年代中期扩充。

举例

逆波兰式通过栈来实现对表达式的运算。例如：

中缀表达式: 5+((1+2) *4)−3 逆波兰式： 512+4 *+3−

逆波兰式的意义

• 当有操作符时就计算，因此，表达式并不是从右至左整体计算而是每次由中心向外计算一部分，这样在复杂运算中就很少导致操作符错误。
• 堆栈自动记录中间结果，这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同，它对表达式的复杂性没有限制。
• 逆波兰表达式中不需要括号，用户只需按照表达式顺序求值，让堆栈自动记录中间结果；同样的，也不需要指定操作符的优先级。
• 逆波兰计算器中，没有“等号”键用于开始计算。
• 逆波兰计算器需要“确认”键用于区分两个相邻的操作数。
• 机器状态永远是一个堆栈状态，堆栈里是需要运算的操作数，栈内不会有操作符。
• 教育意义上，逆波兰计算器的使用者必须懂得要计算的表达式的含义。