逆波兰表达

Posted on | In | | Visitors:

逆波兰表示法

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

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

在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)入栈
2 入栈 17，3
- 减法运算 14 (17,3)出栈；将结果(14)入栈

计算完成时，栈内只有一个操作数，这就是表达式的结果：14
上述运算可以重写为如下运算链方法（用于HP的逆波兰计算器）：
1 2 + 4 * 5 + 3 −

实际意义

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

目前逆波兰的实现有：

-    任何基于栈的程序语言：
-    Forth
-    Factor语言
-    PostScript语言。
-    线上的逆波兰计算器
-    Windows下逆波兰计算器
-    Windows XP下的Microsoft PowerToy calculator
-    手机逆波兰计算器开源的JAVA计算器
-    Palm PDA下的逆波兰计算器
-    Mac OS X计算器
-    Mac OS X和iPhone下的逆波兰计算器
-    Unix下的计算程序dc
-    交互式JavaScript的逆波兰计算器
-    Wikibooks:Ada Programming/Mathematical calculations (Ada语言中的逆波兰计算器)
-    Emacs的lisp lib包: calc
-    基于GTK+的galculator
-    表达式转换