1. 逆波兰表示法
最初，bc程序基于一个叫dc(desk calculator，桌面计算器)的程序。dc是最古老的Unix程序之一，甚至比C语言还要早。实际上，dc的最初版本是使用编程语言B（C的祖先）于1970年编写的。一会之后，我们将进一步讨论bc和dc的关系。但是，现在我将讲授一些有关dc的内容，dc本身就是一个十分有趣的程序，因为像bc一样，它是一个可以立即使用的程序。
我们从一个技术描述开始：dc是一个交互式、不定精确度的计算器，它仿真了一个使用逆波兰表示法(Reverse Polish notation)的栈机器。
很明显，dc并不是那种可以吸引所有人的程序类型：如果对数学或者计算机科学不感兴趣，那么您可以自由地选择跳过该讨论。但是，如果您倾向于技术，那么对dc的理解十分重要，原因有以下几方面。
首先，正如前面所述，dc使用了所谓的逆波兰表示法。尽管这一思想现在对您来说可能没有任何意义，但是它是一个重要的概念，如果您将要学习数学、工程或者计算机科学，那么应该重视这一概念。
其次，为了学习dc，您需要理解栈的思想（稍后解释），这是一个对计算机科学家和程序员都很重要的概念。
最后，使用dc所需的思考方式与使用Unix所需的思考方式相同。因此，花一点时间学习dc（如果乐意的话，可以自己学习如何使用它）将使您更进一步成为Unix人士。
我们将从逆波兰表示法的解释开始关于dc的讨论。在下一节中，将介绍栈的概念。一旦理解了这两个基本思想，您就能够通过联机文档自学如何使用dc。
1920年，一位Jan Lukasiewicz(1878-1956)的波兰数学家观察我们书写算术表达式的方式，发现可以通过将运算符放在操作数之前，使表达式更加紧凑。采用这种方式，我们就能够不使用圆括号或者方括号书写复杂的表达式。下面示范一个简短的例子来描述这一思想。
假设您希望将34加上25，然后把和乘以15。使用标准的表示法时，写法如下所：
(34 + 25) * 15
因为运算符（在这个例子中是+（加号）和*（乘号）位于操作数的中间，所以我们称这种表示法为中缀表示法（infix notation）。 Lukasiewicz的系统使用前缀表示法(prefix notation)，在这种表示法中，先书写运算符，然后才是操作数。例如：
* + 34 25 15
为了求前缀表示法的值，我们从左向右，每次一个的处理元素。在这个例子中，首先是*运算符，它告诉我们只要获得两个数字就执行一个乘法运算。然后我们遇到+运算符，它告诉我们只要获得两个数字就执行一个加法运算。
接下来，连续获得两个数字34和25，因此我们执行加法运算，得到一个和59。记住这个59，我们继续，然后遇到了数字15。现在可以执行乘法59*15，获得最后的结果885。
为了纪念Lukasiewicz（一名著名的数学家、逻辑学家和哲学家），通常将前缀表示法成为波兰表示法（Polish notation）对于计算机科学家来说，波兰表示法十分重要，因为它紧凑、直接，而且求值过程很高效。
1957年，奥地利计算机科学家Charles Hamblin撰写了两篇篇论文，在这两篇论文中，他提议在基于栈的计算机系统中使用波兰表示法的一种变体（我们将在下一节中讨论栈）。他描述的变体将是运算符放在操作数之后，这种表示法称为后缀表示法（postfix notation）
为了描述后缀表示法，我们重新考虑前面的表达式。在后缀表示法中它如下所示：
34 25 + 15 *
为了求这种表达式的值，我们从左向右处理元素。首先，看到两个数字34和25。这两个数字我们必须记住。接下来，我们看到+运算符，这告诉我们将之前两个可用的数字加起来。在这个例子中将34加上25得到59，这个数字我们也必须记住。
接下来，我们看到数字15，这个数字也要记住。最后，看到*运算符，它告诉我们将后两个数乘在一起。在这个例子中，两个数字是59和15，将它们乘起来获得的结果是885。
后缀表示法特别适合自动计算，这是因为表达式可以通过记住数字并应用遇到的运算符，以一种直接的方式从左向右求值。对于中缀表示法，括号和其他类型的优先级（例如，乘法必须优先于加法完成）通常要某些运算必须一直等到其他运算完成时才能进行。而后缀表示法就没有这种问题。
为了纪念Lukasiewiez，后缀表示法通常称为逆波兰表示法或者简称为RPN。多年以来波兰表示法和逆波兰表示法在许多计算机系统中都得到广泛的应用。例如,Lisp编程语言和Tcl脚本语言中就使用了波兰（前缀）表示法。Forth编程语言和PostScript页面描述语言就使用了逆波兰（后缀）表示法。
或许RPN最有名的应用就是作为HP计算器的基础。HP计算器已被广大科学家和工程师使用了许多年。第一个此类计算器是HP 9100，于l968年发明。
从那时起，RPN器就开始流行，因为 一旦您理解了RPN，相对于传统的中缀表示，它要快许多，并且使用更容易。例如，当您使用RPN计算器时，每个计算的结果会立即显示。这意味着输入运算时可以看到局部结果，从而使错误的捕捉相对容易，而使用传统中缀表示法的计算器，情况就不是这样了。如果您输入了一个使用标准优先级规则的表达式，那么除非整个运算结束，否则结果是不会显示出来的。
1970年，贝尔实验室的一名研究人员Robert Morris，受HP计算器的启发，使用RPN开发了一个基于Unix的交互式计算器程序。Morris将这个程序称为dc (desk calculator，桌面计算器)。De是一个神奇的工具，但是它要求用户学习如何使用RPN。
几年之后，Morris和另一名研究人员Lorinda Cherry一起编写了另个名叫bc的程序，该程序允许用户使用更传统的中缀表示法书写算式。bc的工作方式是将输入转换成RPN，然后调用dc完成实际工作。换句话说，bc是dc的“前端”。这允许人们选择他们喜爱的系统；dc的后缀表示法或者bc的中缀表示法。
若干年之后，作为GNU项目，bc作为一个独立的程序完全进行了重写。因为许多现代的Unix(包括Linux和FreeBSD)都使用GNU实用工具，所以当您现在使用bc时，使用的是一个不再依赖于dc的独立程序。当然，dc仍然可以单独使用。
2. 基于栈的计算器：dc
考虑下述RPN(后缀)表示法的例子：
34 25 + 15 *
dc以上一节中描述的方式求这个表达式的值，从左向右，每次读取一个元素。dc每遇到一个数字，这个数字的值将被记住。dc每遇到一个运算符，都必须执行合适的运算,而结果必须被记住。
这就出现了一个问题，dc如何记录各个必须记住的元素呢？答案就是用所谓的栈。
在计算机科学中，有各种不同的数据结构可以用来存放数据。每种类型的数据结构能够根据自己的一组明确规则存储和检索数据。其中最常见的数据结构有列表、链表、关联数组、哈希表、栈、队列、双头队列（双端队列）以及多种基于树的结构。在本节巾，我们将集中讨论栈，因为它就是dc程序使用的数据结构。
栈是一种根据“后进先出（Last in first out，LIFO)”过程每次存储或者检索一个数据元素的数据结构。下面是栈的工作方式。
刚开始时栈是空的。为了在栈中存储一个数据元素，需要将数据元素压入(push)栈中。现在数据就位于栈的顶部。每次一个，您可以在栈中压入任意多的数据元素。每压入一个元素，栈中的所有元素都向下移一级。因此，在任何时候，栈的顶部都包含刚刚压入到栈中的数据。从栈中检索数据时，只需从栈的项部取数据即可。当这样做时，我们称之为栈的弹出(pop)运算。
换句话说，当弹出栈时，会检索压入到栈中的最后一个值。这就是为什么将栈描述为LIFO(后进先出)的原因。
下面举一个栈的具体例子，想象一下自助餐厅中的弹簧支承的盘子叠。盘子一个一个地压入到“栈”中。当需要盘子时，必须将栈顶部的那一个盘子弹出。您不能获取其他的盘子。如果基于某些原因，需要最底部的那个盘子，那么您不得不将该盘子顶部的所有盘子逐个弹出。
dc程序使用栈以这种方式解释RPN表示的算术表达式。在这样做时，dc遵循一个简单的过程：从左向右读取表达式，每次一个元素。如果遇到的是数值，则将它压入到栈中。如果遇到的是运算符，则从栈中弹出合适数量的元素，执行运算，然后将结果压入至栈中。
为了描述该运算过程，我们重新考虑前面的例子：
34 25+ 15*
下面是dc解释这个表达式的步骤:
(1) 读取值34并将它压入到栈中。
栈中包含有：34
(2)读取值25并将它压入到栈中。
栈中包含有：25
(3)读取+（加号）。为了执行加法，需要两个值，因此……
(4)从栈中弹出25和34，并将它们相加。将结果(59)压入到栈中。
栈中包含有：59
(5) 读取15并将它压入到栈中。
栈中包含有：15 59
(6)读取*(乘号)。为了执行乘法，需要两个值，因此…
(7) 从栈中弹出15和59，并将它们相乘。将结果(885)压入到栈中。
栈中包含有：855
如果还不能立即掌握RPN，那么您不用担心。通过多练习dc程序，您一定能够体会出来。实际上真正理解RPN的最好方法就是多多练习。
在我们的例子中，示范了每个步骤上栈中的内容。而在dc中，您看不到栈。但是，在任何时候都可以使用P(print, 打印)命令显示栈的顶部。为了示范该命令的工作方式，我们启动了dc程序，然后输入下述两行（不要忘记了在每行的末尾按<Retum>键。
34 25 + 15 *
P
在输入了第一行之后，dc程序执行运算。但是，您看不到任何东西。一旦您输入了第二行（p命令），dc将显示栈顶元素的值，在这个例子中是885，这是上一个运算的结果。
如果希望看到这个栈，可以使用f命令：
f
为什么dc不能在每次输入一个新行时自动显示栈顶元素的值呢？答案是如果dc在每输入一行时显示一些东西，那么它将导致屏幕混乱。实际上，dc(像大多数Unix程序一样)，尽可能不显示内容。需要时，您自己可以查看栈顶元素的值。
为了帮助您开始使用dc，下表概括了一些最重要的dc命令。除了该列表之外，自己学习使用dc的最好方法就是阅读联机手册并多加练习。查看dc手册页面的命令是：
man dc
dc中小数点后面的数字称为“精确度”。精确度默认值为0位。为了修改小数点的位数，需要将位数压入到栈中,然后输入k命令。这个值可以任意大。例如，将精确度修改为14位数字，可以使用：
14 K
如果要显示当前的精确度，可以使用K（大写“K”）命令——这将把当前的精确度压入到栈顶，然后再使用p命令显示实际值：
K p
最后，在停止dc时，或者通过按下^D表示已经没有数据了，或者使用q(quit,退出)命令。
最初，bc程序基于一个叫dc(desk calculator，桌面计算器)的程序。dc是最古老的Unix程序之一，甚至比C语言还要早。实际上，dc的最初版本是使用编程语言B（C的祖先）于1970年编写的。一会之后，我们将进一步讨论bc和dc的关系。但是，现在我将讲授一些有关dc的内容，dc本身就是一个十分有趣的程序，因为像bc一样，它是一个可以立即使用的程序。
我们从一个技术描述开始：dc是一个交互式、不定精确度的计算器，它仿真了一个使用逆波兰表示法(Reverse Polish notation)的栈机器。
很明显，dc并不是那种可以吸引所有人的程序类型：如果对数学或者计算机科学不感兴趣，那么您可以自由地选择跳过该讨论。但是，如果您倾向于技术，那么对dc的理解十分重要，原因有以下几方面。
首先，正如前面所述，dc使用了所谓的逆波兰表示法。尽管这一思想现在对您来说可能没有任何意义，但是它是一个重要的概念，如果您将要学习数学、工程或者计算机科学，那么应该重视这一概念。
其次，为了学习dc，您需要理解栈的思想（稍后解释），这是一个对计算机科学家和程序员都很重要的概念。
最后，使用dc所需的思考方式与使用Unix所需的思考方式相同。因此，花一点时间学习dc（如果乐意的话，可以自己学习如何使用它）将使您更进一步成为Unix人士。
我们将从逆波兰表示法的解释开始关于dc的讨论。在下一节中，将介绍栈的概念。一旦理解了这两个基本思想，您就能够通过联机文档自学如何使用dc。
1920年，一位Jan Lukasiewicz(1878-1956)的波兰数学家观察我们书写算术表达式的方式，发现可以通过将运算符放在操作数之前，使表达式更加紧凑。采用这种方式，我们就能够不使用圆括号或者方括号书写复杂的表达式。下面示范一个简短的例子来描述这一思想。
假设您希望将34加上25，然后把和乘以15。使用标准的表示法时，写法如下所：
(34 + 25) * 15
因为运算符（在这个例子中是+（加号）和*（乘号）位于操作数的中间，所以我们称这种表示法为中缀表示法（infix notation）。 Lukasiewicz的系统使用前缀表示法(prefix notation)，在这种表示法中，先书写运算符，然后才是操作数。例如：
* + 34 25 15
为了求前缀表示法的值，我们从左向右，每次一个的处理元素。在这个例子中，首先是*运算符，它告诉我们只要获得两个数字就执行一个乘法运算。然后我们遇到+运算符，它告诉我们只要获得两个数字就执行一个加法运算。
接下来，连续获得两个数字34和25，因此我们执行加法运算，得到一个和59。记住这个59，我们继续，然后遇到了数字15。现在可以执行乘法59*15，获得最后的结果885。
为了纪念Lukasiewicz（一名著名的数学家、逻辑学家和哲学家），通常将前缀表示法成为波兰表示法（Polish notation）对于计算机科学家来说，波兰表示法十分重要，因为它紧凑、直接，而且求值过程很高效。
1957年，奥地利计算机科学家Charles Hamblin撰写了两篇篇论文，在这两篇论文中，他提议在基于栈的计算机系统中使用波兰表示法的一种变体（我们将在下一节中讨论栈）。他描述的变体将是运算符放在操作数之后，这种表示法称为后缀表示法（postfix notation）
为了描述后缀表示法，我们重新考虑前面的表达式。在后缀表示法中它如下所示：
34 25 + 15 *
为了求这种表达式的值，我们从左向右处理元素。首先，看到两个数字34和25。这两个数字我们必须记住。接下来，我们看到+运算符，这告诉我们将之前两个可用的数字加起来。在这个例子中将34加上25得到59，这个数字我们也必须记住。
接下来，我们看到数字15，这个数字也要记住。最后，看到*运算符，它告诉我们将后两个数乘在一起。在这个例子中，两个数字是59和15，将它们乘起来获得的结果是885。
后缀表示法特别适合自动计算，这是因为表达式可以通过记住数字并应用遇到的运算符，以一种直接的方式从左向右求值。对于中缀表示法，括号和其他类型的优先级（例如，乘法必须优先于加法完成）通常要某些运算必须一直等到其他运算完成时才能进行。而后缀表示法就没有这种问题。
为了纪念Lukasiewiez，后缀表示法通常称为逆波兰表示法或者简称为RPN。多年以来波兰表示法和逆波兰表示法在许多计算机系统中都得到广泛的应用。例如,Lisp编程语言和Tcl脚本语言中就使用了波兰（前缀）表示法。Forth编程语言和PostScript页面描述语言就使用了逆波兰（后缀）表示法。
或许RPN最有名的应用就是作为HP计算器的基础。HP计算器已被广大科学家和工程师使用了许多年。第一个此类计算器是HP 9100，于l968年发明。
从那时起，RPN器就开始流行，因为 一旦您理解了RPN，相对于传统的中缀表示，它要快许多，并且使用更容易。例如，当您使用RPN计算器时，每个计算的结果会立即显示。这意味着输入运算时可以看到局部结果，从而使错误的捕捉相对容易，而使用传统中缀表示法的计算器，情况就不是这样了。如果您输入了一个使用标准优先级规则的表达式，那么除非整个运算结束，否则结果是不会显示出来的。
1970年，贝尔实验室的一名研究人员Robert Morris，受HP计算器的启发，使用RPN开发了一个基于Unix的交互式计算器程序。Morris将这个程序称为dc (desk calculator，桌面计算器)。De是一个神奇的工具，但是它要求用户学习如何使用RPN。
几年之后，Morris和另一名研究人员Lorinda Cherry一起编写了另个名叫bc的程序，该程序允许用户使用更传统的中缀表示法书写算式。bc的工作方式是将输入转换成RPN，然后调用dc完成实际工作。换句话说，bc是dc的“前端”。这允许人们选择他们喜爱的系统；dc的后缀表示法或者bc的中缀表示法。
若干年之后，作为GNU项目，bc作为一个独立的程序完全进行了重写。因为许多现代的Unix(包括Linux和FreeBSD)都使用GNU实用工具，所以当您现在使用bc时，使用的是一个不再依赖于dc的独立程序。当然，dc仍然可以单独使用。
2. 基于栈的计算器：dc
考虑下述RPN(后缀)表示法的例子：
34 25 + 15 *
dc以上一节中描述的方式求这个表达式的值，从左向右，每次读取一个元素。dc每遇到一个数字，这个数字的值将被记住。dc每遇到一个运算符，都必须执行合适的运算,而结果必须被记住。
这就出现了一个问题，dc如何记录各个必须记住的元素呢？答案就是用所谓的栈。
在计算机科学中，有各种不同的数据结构可以用来存放数据。每种类型的数据结构能够根据自己的一组明确规则存储和检索数据。其中最常见的数据结构有列表、链表、关联数组、哈希表、栈、队列、双头队列（双端队列）以及多种基于树的结构。在本节巾，我们将集中讨论栈，因为它就是dc程序使用的数据结构。
栈是一种根据“后进先出（Last in first out，LIFO)”过程每次存储或者检索一个数据元素的数据结构。下面是栈的工作方式。
刚开始时栈是空的。为了在栈中存储一个数据元素，需要将数据元素压入(push)栈中。现在数据就位于栈的顶部。每次一个，您可以在栈中压入任意多的数据元素。每压入一个元素，栈中的所有元素都向下移一级。因此，在任何时候，栈的顶部都包含刚刚压入到栈中的数据。从栈中检索数据时，只需从栈的项部取数据即可。当这样做时，我们称之为栈的弹出(pop)运算。
换句话说，当弹出栈时，会检索压入到栈中的最后一个值。这就是为什么将栈描述为LIFO(后进先出)的原因。
下面举一个栈的具体例子，想象一下自助餐厅中的弹簧支承的盘子叠。盘子一个一个地压入到“栈”中。当需要盘子时，必须将栈顶部的那一个盘子弹出。您不能获取其他的盘子。如果基于某些原因，需要最底部的那个盘子，那么您不得不将该盘子顶部的所有盘子逐个弹出。
dc程序使用栈以这种方式解释RPN表示的算术表达式。在这样做时，dc遵循一个简单的过程：从左向右读取表达式，每次一个元素。如果遇到的是数值，则将它压入到栈中。如果遇到的是运算符，则从栈中弹出合适数量的元素，执行运算，然后将结果压入至栈中。
为了描述该运算过程，我们重新考虑前面的例子：
34 25+ 15*
下面是dc解释这个表达式的步骤:
(1) 读取值34并将它压入到栈中。
栈中包含有：34
(2)读取值25并将它压入到栈中。
栈中包含有：25
(3)读取+（加号）。为了执行加法，需要两个值，因此……
(4)从栈中弹出25和34，并将它们相加。将结果(59)压入到栈中。
栈中包含有：59
(5) 读取15并将它压入到栈中。
栈中包含有：15 59
(6)读取*(乘号)。为了执行乘法，需要两个值，因此…
(7) 从栈中弹出15和59，并将它们相乘。将结果(885)压入到栈中。
栈中包含有：855
如果还不能立即掌握RPN，那么您不用担心。通过多练习dc程序，您一定能够体会出来。实际上真正理解RPN的最好方法就是多多练习。
在我们的例子中，示范了每个步骤上栈中的内容。而在dc中，您看不到栈。但是，在任何时候都可以使用P(print, 打印)命令显示栈的顶部。为了示范该命令的工作方式，我们启动了dc程序，然后输入下述两行（不要忘记了在每行的末尾按<Retum>键。
34 25 + 15 *
P
在输入了第一行之后，dc程序执行运算。但是，您看不到任何东西。一旦您输入了第二行（p命令），dc将显示栈顶元素的值，在这个例子中是885，这是上一个运算的结果。
如果希望看到这个栈，可以使用f命令：
f
为什么dc不能在每次输入一个新行时自动显示栈顶元素的值呢？答案是如果dc在每输入一行时显示一些东西，那么它将导致屏幕混乱。实际上，dc(像大多数Unix程序一样)，尽可能不显示内容。需要时，您自己可以查看栈顶元素的值。
为了帮助您开始使用dc，下表概括了一些最重要的dc命令。除了该列表之外，自己学习使用dc的最好方法就是阅读联机手册并多加练习。查看dc手册页面的命令是：
man dc
dc中小数点后面的数字称为“精确度”。精确度默认值为0位。为了修改小数点的位数，需要将位数压入到栈中,然后输入k命令。这个值可以任意大。例如，将精确度修改为14位数字，可以使用：
14 K
如果要显示当前的精确度，可以使用K（大写“K”）命令——这将把当前的精确度压入到栈顶，然后再使用p命令显示实际值：
K p
最后，在停止dc时，或者通过按下^D表示已经没有数据了，或者使用q(quit,退出)命令。
命令
|
含义
|
q
|
退出
|
p
|
显示栈顶
|
n
|
弹出栈并显示值
|
f
|
显示栈的全部内容
|
c
|
清除（清空）栈
|
d
|
复制栈顶值
|
r
|
反转（交换）栈顶的两个值
|
+
|
弹出两个值，相加，然后将和压入到栈中
|
-
|
弹出两个值，相减，然后将差压入到栈中
|
*
|
弹出两个值，相乘，然后将积压入到栈中
|
/
|
弹出两个值，相除，然后将商压入到栈中
|
%
|
弹出两个值，相除，然后将余数压入到栈中
|
~
|
弹出两个值，相除，然后将商压入到栈中，然后再将余数压入到栈中
|
^
|
弹出两个值，第一个数是第二个数的幂指数，然后再将 余数压入到栈中
|
v
|
弹出一个值，求平方根，然后将结果压入到栈中
|
k
|
弹出一个值，使用这个值设置精确度
|
提示： 如果喜欢数学或者科学思考，那么您可以发现使用dc非常有乐趣。这样做时，您将发现dc不仅仅是消遣。为了学习如何使用该程序，您需要掌握逆波兰表示法的思想，并且还要学习如何使用栈，而这两个概念都是不容易理解的概念。但是，一旦掌握了这些思 想，您将发现dc是一个高效、设计良好的工具，非常易于使用。 如果再回到前面，那么您将看到我们对Unix所做的两个一般性注释：Unix易于使用，但难于学习。您需要首先从基本的知识开始学习，然后再根据自己的需要，学习其他知识。 您能看出dc正好适合这种范式吗？dc的使用非常简单。但是学习比较困难。您开始时要学习基本知识，然后再根据自己的需要体验它。因此，如果有时间练习使用dc，那么您不仅在学习使用一个有趣的工具，而且还在训练自己以Unix的方式思考
沒有留言:
張貼留言