逆波兰表示法(Reverse Polish Notation)

翻译自Harley Hahn’s Guide to Unix and Linux
最 初,bc这个程序是基于dc(desk calculator)程序开发的. dc是最古老的Unix程序之一,它的出现甚至比C语言还要早. 事实上, dc的最初版本是在1970年用C语言的祖先即B语言编写的. 我们待会将讨论bc和dc之间的联系. 但现在我想告诉你的是关于dc的一些知识. dc本身就是一个很有趣的工具, 这是一个用户可以立刻使用的程序.

首先给dc一个技术性的描述: dc是使用逆波兰表示法来模拟堆栈机器的一个交互式,提供任意精确度的计算器.

显然, dc不是一个受所有人欢迎的程序. 如果你对数学或计算机科学没有兴趣的话, 完全可以跳过下面的内容. 但如果你是一个技术性人员, 理解dc计算器是非常重要的.有下面几点原因.

• 第一,正如我刚才提到的, dc计算器使用逆波兰表示法(RPN). 虽然现在它对你来说无足轻重, 但如果你现在学习的是数学,工程学或计算机科学的话,理解逆波兰表示法很重要.
• 第二, 要学习dc计算器, 你必须理解什么是堆栈(stack). 堆栈对于计算机科学家和程序员来说很重要.
• 第三, 使用dc计算器所需的思维方式正是使用Unix所需要的思维方式. 这样,花点时间学习dc将使你向成为Unix人士的目标迈进了一大步.

我先解释什么是逆波兰表示法,然后在下一个部分讨论堆栈. 理解了这两个基本概念, 你就有能力使用在线文档来教会自己如何使用dc计算器了.

1920年,波兰数学家扬*武卡谢维奇(1878-1956)观察到, 把运算符放在运算数前面, 可以使我们书写算术表达式的方式变得更加紧凑. 通过这种方式, 我们不借助圆括号也可以书写复杂的表达式.下面的例子将阐明这一思想.

假如你要把34和25相加,然后用15乘以它们的和. 标准表示法为

(34+25)*15

在这个例子中,有两个运算符,+(加号)和*(乘号)被放置在运算数的中间. 我们称之为中缀表示法(Infix Notation).

武卡谢维奇用的的前缀表示法(Prefix Notation), 即先写运算符再写运算数. 例如:

* + 34 25 15

为 了求前缀表达式的値,我们从左至右一次只处理一个元素. 在这个例子中, 先从第一个元素*(乘号)开始, 它告诉我们一旦乘号后面有两个数字就进行乘法运算. 第二个元素是+加号, 它告诉我们一旦加号后面有两个数字就进行加法运算.接下来, 我们看到有两个连续的数字34和25, 所以我们进行加法运算,和为59. 现在数字59可以替换掉 + 34 25 这三个元素. 然后继续, 我们看到数字15. 现在我们可以进行乘法运算59*15, 这个前缀表达式的结果为885.

为了纪念武卡谢维奇这位享有声誉的数学家,逻辑学家和哲学家, 前缀表示法经常被称为波兰表示法. 对计算机科学家来说,波兰表示法因为紧凑,简单,计算效率高而变得重要.

1957年,澳大利亚计算机科学家查尔斯*汉布林在他写的两篇论文中提议使用一种基于堆栈的类波兰表示法. (我们将在在下一部分讨论堆栈) 他把运算符放在运算数的后面,也就是后缀表示法.

为了阐明后缀表示法, 我们重新审视上面的前缀表达式.用后缀表示法这个表达式变成:

34 25 + 15 *

为 了求后缀表达式的值,我们从左至右处理其中的元素. 首先我们看到有两个数字34和25,先记住这两个数字. 然后我们看到+加号运算符,它告诉我们把前面两个数字相加. 在此例中,把34和25相加得到59.记住59.接下来,我们看到数字15,所以现在我们又有了两个数字59和15. 最后我们看到*乘法运算符,它告诉我们把前面两个数字相乘. 在此例中,我们把59和15相乘得到最后结果885.

后缀表示法对自动化计算特别适用,因为表达式的值可以用一种简单的方式求得-从左至右,每遇到两个数字和一个运算符便进行一次运算. 在中缀表示法中,圆括号和其他优先运算符-比如乘法优先于加法-通常要求延后运算直到其他运算完成.而在后缀表示法中不必延后运算.

为 了纪念武卡谢维奇, 后缀表示法通常被称为逆波兰表示法(RPN).在过去的几十年里,波兰表示法和逆波兰表示法被应用于各种各样的计算机系统. 例如Lisp编程语言和Tcl脚本语言使用波兰(前缀)表示法. Forth编程语言和PostScript页面描述语言使用逆波兰(后缀)表示法.

被科学家和工程师使用了多年的HP计算器或许是RPN最为著名的应用了.第一批基于RPN的HP计算器是1968年面世的HP 9100.

自 那以后,RPN计算器变得非常流行. 因为一旦你理解了RPN, 那么跟中缀表示法相比既快速又容易. 例如,当你使用RPN计算器的时候,每一次计算的结果都会立刻被显示出来. 这意味着当你输入表达式后,你将看到计算过程的部分结果,这使发现错误变得非常容易. 传统的中缀表示法不能做到这一点. 如果你输入一个使用标准优先级法则的表达式,必须等到全部计算完成后才能看到结果.

1970年,贝尔实验室的一名研究人员罗伯特*莫里斯受HP计算器的启发,用RPN为Unix系统开发了一个交互式的计算器程序,他取名为dc(desk calculator). dc是一个极好的工具,但它要求用户先掌握RPN.

几 年后,莫里斯和另外一个研究人员Lorinda Cherry,编写了一个叫bc的程序. bc允许用户使用传统的中缀法输入表达式, bc将把中缀表达式转换为后缀表达式,然后调用dc来进行实际的运算.换句话说,bc是dc的前端. 这让用户可以使用他们偏爱的表示法:后缀表示法用dc,中缀表示法用bc.

又过了若干年,作为GNU计划的一部分, bc程序被重新编写,从而有了一个独立于dc的bc. 由于现在很多类型的Unix(包括Linux和FreeBSD)使用GNU工具,当你使用bc时,很可能你使用的是一个不依赖于dc的bc计算器. 当然,你仍然可以使用单独的dc计算器.