逆波兰表示法

2017-10-16

出处：族谱网

作者：阿族小谱

浏览:673次

转发:0次

评论:0

解释逆波兰记法中，操作符置于操作数的后面。例如表达“三加四”时，写作“34+”，而不是“3+4”。如果有多个操作符，操作符置于第二个操作数的后面，所以常规中缀记法的“3-4+5”在逆波兰记法中写作“34-5+”：先3减去4，再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3-4*5”与“（3-4）*5”不相同，但后缀记法中前者写做“345*-”，无歧义地表示“3(45*)−”；后者写做“34-5*”。逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，并且能很快求值。注意：逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法“/63”的逆波兰记法是“63/”而不是“36/”；数字

解释

逆波兰记法中，操作符置于操作数的后面。例如表达“三加四”时，写作“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有输入符号

IF栈内只有一个值

ELSE多于一个值

例子

中缀表达式“5 + ((1 + 2) * 4) − 3”写作

下表给出了该逆波兰表达式从左至右求值的过程，堆栈栏给出了中间值，用于跟踪算法。

计算完成时，栈内只有一个操作数，这就是表达式的结果：14

上述运算可以重写为如下运算链方法（用于HP的逆波兰计算器）：

实现

第一代实现了逆波兰架构的电子计算机是英国电气公司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下逆波兰计算器