逆波兰表示法
|
| 前缀表示法 （+ 3 4 ） |
| 中缀表示法 （3 + 4） |
| 后缀表示法 （3 4 + ） |
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰结构由弗里德里希·鲍尔（Friedrich L. Bauer）和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林（Charles Hamblin）在1960年代中期扩充[1][2]
在1960和1970年代，逆波兰记法广泛地被用于台式计算器，因此也在普通公众（工程、商业和金融领域）中使用。
下面大部分是关于二元运算，一个一元运算使用逆波兰记法的例子是阶乘的记法。
解释
逆波兰记法中，操作符置于操作数的后面。例如表达“三加四”时，写作“3 4 +”，而不是“3 + 4”。如果有多个操作符，操作符置于第二个操作数的后面，所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”：先3减去4，再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 * 5”与“（3 - 4）*5”不相同，但后缀记法中前者写做“3 4 5 * -”，无歧义地表示“3 (4 5 *) −”；后者写做“3 4 - 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，并且能很快求值。
注意：逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”；数字的数位写法也是常规顺序。
与中缀记法的转换
艾兹格·迪科斯彻引入了调度场算法，用于将中缀表达式转换为后缀形式。因其操作类似于火车編組場而得名。 大多数操作符优先级解析器(解析器用简单的查表操作即可实现，优先级表由开发者自己定制，在不同的应用场景中，开发者可自由改变操作符的优先级)能转换为处理后缀表达式，实际中，一般构造抽象语法树，树的后序遍历即为逆波兰记法。
逆波兰表达式求值
伪代码
- while有输入符号
- 读入下一个符号X
- IF X是一个操作数
- 入栈
- ELSE IF X是一个操作符
- 有一个先验的表格给出该操作符需要n个参数
- IF堆栈中少于n个操作数
- （错误） 用户没有输入足够的操作数
- Else，n个操作数出栈
- 计算操作符。
- 将计算所得的值入栈
- IF栈内只有一个值
- 这个值就是整个计算式的结果
- ELSE多于一个值
- （错误） 用户输入了多余的操作数
例子
中缀表达式“5 + ((1 + 2) * 4) − 3”写作
- 5 1 2 + 4 * + 3 −
下表给出了该逆波兰表达式从左至右求值的过程，堆栈栏给出了中间值，用于跟踪算法。
| 输入 | 操作 | 堆栈 | 注释 |
|---|---|---|---|
| 5 | 入栈 | 5 | |
| 1 | 入栈 | 5, 1 | |
| 2 | 入栈 | 5, 1, 2 | |
| + | 加法运算 | 5, 3 | (1, 2)出栈；将结果（3）入栈 |
| 4 | 入栈 | 5, 3, 4 | |
| * | 乘法运算 | 5, 12 | (3, 4)出栈；将结果（12）入栈 |
| + | 加法运算 | 17 | (5, 12)出栈；将结果 (17)入栈 |
| 3 | 入栈 | 17, 3 | |
| − | 减法运算 | 14 | (17, 3)出栈；将结果（14）入栈 |
计算完成时，栈内只有一个操作数，这就是表达式的结果：14
上述运算可以重写为如下运算链方法（用于HP的逆波兰计算器）：[3]
- 1 2 + 4 * 5 + 3 −
实现
第一代实现了逆波兰架构的电子计算机是英国电气公司1963年交付使用的KDF9和美国的Burroughs B5000。Friden公司在它1963年推出的EC-130中，将逆波兰表达式引入了台式计算器市场。惠普1968年设计了9100A逆波兰计算器，首台手持式计算器HP-35也使用逆波兰表达式，惠普在HP-10A之前的所有手持计算器（包括科学计算，金融和可编程）中使用了逆波兰表达式，并在1980年代晚期的LCD显示计算器如HP-10C, HP-11C, HP-15C, HP-16C，等都是用了逆波兰表达式。
实际意义
- 当有操作符时就计算，因此，表达式并不是从右至左整体计算而是每次由中心向外计算一部分，这样在复杂运算中就很少导致操作符错误。
- 堆栈自动记录中间结果，这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同，它对表达式的复杂性没有限制。
- 逆波兰表达式中不需要括号，用户只需按照表达式顺序求值，让堆栈自动记录中间结果；同样的，也不需要指定操作符的优先级。
- 逆波兰计算器中，没有“等号”键用于开始计算。
- 逆波兰计算器需要“确认”键用于区分两个相邻的操作数。
- 机器状态永远是一个堆栈状态，堆栈里是需要运算的操作数，栈内不会有操作符。
- 教育意义上，逆波兰计算器的使用者必须懂得要计算的表达式的含义。
目前逆波兰的实现有：
- 任何基于栈的程序语言：
- 线上的逆波兰计算器
- Windows下逆波兰计算器
- Windows XP下的Microsoft PowerToy calculator
- 手机逆波兰计算器开源的JAVA计算器
- Palm PDA下的逆波兰计算器
- Mac OS X计算器
- Mac OS X和iPhone下的逆波兰计算器
- Unix下的计算程序dc
- 交互式JavaScript的逆波兰计算器：[2]和[3]
- Wikibooks:Ada Programming/Mathematical calculations (Ada语言中的逆波兰计算器)
- Emacs的lisp lib包: calc
- 基于GTK+的galculator
- 表达式转换[4]
注释
- ^ "Charles L. Hamblin and his work" by Peter McBurney
- ^ "Charles L. Hamblin: Computer Pioneer" by Peter McBurney, July 27, 2008. "Hamblin soon became aware of the problems of (a) computing mathematical formulae containing brackets, and (b) the memory overhead in having dealing with memory stores each of which had its own name. One solution to the first problem was Jan Lukasiewicz's Polish notation, which enables a writer of mathematical notation to instruct a reader the order in which to execute the operations (e.g. addition, multiplication, etc) without using brackets. Polish notation achieves this by having an operator (+, *, etc) precede the operands to which it applies, e.g., +ab, instead of the usual, a+b. Hamblin, with his training in formal logic, knew of Lukasiewicz's work."
- ^ "As was demonstrated in the Algebraic mode, it is usually easier (fewer keystrokes) in working a problem like this to begin with the arithmetic operations inside the parentheses first."[1]
参见
参考
- RPN or DAL? A brief analysis of Reverse Polish Notation against Direct Algebraic Logic – By James Redin
- Postfix Notation Mini-Lecture – By Bob Brown
- Fith: An Alien Conlang With A LIFO Grammar – By Jeffrey Henning
- Good Ideas, Through the Looking Glass - By Nick Wurth