逆波兰表示法

编辑:画像网互动百科 时间:2020-07-07 17:42:57
编辑 锁定
逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。
中文名
逆波兰表示法
外文名
Reverse Polish notation
别    名
逆波兰记法
发明者
扬·武卡谢维奇

逆波兰表示法简介

编辑
逆波兰表示法(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 /”;数字的数位写法也是常规顺序。

逆波兰表示法与中缀记法的转换

编辑
艾兹格·迪科斯彻引入了shunting yard算法,用于将中缀表达式转换为后缀形式。因其操作类似于火车编组场而得名。 大多数操作符优先级解析器能转换为处理后缀表达式,实际中,一般构造抽象语法树,树的后序遍历即为逆波兰记法。

逆波兰表示法逆波兰表达式求值

编辑
伪代码
while有输入符号
读入下一个符号
IF是一个操作数
入栈
ELSE IF是一个操作符
有一个先验的表格给出该操作符需要n个参数
IF堆栈中少于n个操作数
(错误) 用户没有输入足够的操作数
Else,n个操作数出栈
计算操作符。
将计算所得的值入栈
IF栈内只有一个值
这个值就是整个计算式的结果
ELSE多于一个值
(错误) 用户输入了多余的操作数

逆波兰表示法实现

编辑
第一代实现了逆波兰架构的电子计算机是英国电气公司1963年交付使用的KDF9和美国的Burroughs B5000。Friden公司在它1963年推出的EC-130中,将逆波兰表达式引入了台式计算器市场。惠普1968年设计了9100A逆波兰计算器,首台手持式计算器HP-35也使用逆波兰表达式,惠普在HP-10A之前的所有手持计算器(包括科学计算,金融和可编程)中使用了逆波兰表达式,并在1980年代晚期的LCD显示计算器如HP-10C, HP-11C, HP-15C, HP-16C,等都是用了逆波兰表达式。

逆波兰表示法实际意义

编辑
当有操作符时就计算,因此,表达式并不是从右至左整体计算而是每次由中心向外计算一部分,这样在复杂运算中就很少导致操作符错误。
堆栈自动记录中间结果,这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同,它对表达式的复杂性没有限制。
逆波兰表达式中不需要括号,用户只需按照表达式顺序求值,让堆栈自动记录中间结果;同样的,也不需要指定操作符的优先级。
逆波兰计算器中,没有“等号”键用于开始计算。
逆波兰计算器需要“确认”键用于区分两个相邻的操作数。
机器状态永远是一个堆栈状态,堆栈里是需要运算的操作数,栈内不会有操作符。
教育意义上,逆波兰计算器的使用者必须懂得要计算的表达式的含义。
目前逆波兰的实现有:
任何基于栈的程序语言:
Forth
Factor语言
PostScript语言。
Windows下逆波兰计算器
Windows XP下的Microsoft PowerToy calculator
手机逆波兰计算器开源的JAVA计算器
Palm PDA下的逆波兰计算器
Mac OS X计算器
Mac OS X和iPhone下的逆波兰计算器
Unix下的计算程序dc
交互式JavaScript的逆波兰计算器:
rpn-calculator
Wikibooks:Ada Programming/Mathematical calculations (Ada语言中的逆波兰计算器)
Emacs的lisp lib包: calc
基于GTK+的galculator
表达式转换
词条标签:
计算机学 理学