C1：计算器如何工作/如何编写一个？

引言

这是开发计算器系列教程的第一部分，理论部分。在这个系列中，我将用 C++ 编写一个功能完整的计算器应用程序。计划支持不同的数字系统、括号和科学计算器上的可用函数。

让我们开始吧。

去年一个失眠的夜晚，我问自己，计算器是如何工作的？那时我正在为我的 Jump’n’Run 框架开发一个小型基于堆栈的脚本引擎。完成后，我想知道计算器是否可以用堆栈实现。第二天，我上网查了一下计算器一般是如何工作的，但没有找到任何好的解释（实际上直到今天我也不知道我的方法是否是通用方法，或者是否有更好或更容易的方法）。所以，我决定尝试一下。一无所知，我只是开始分析我计算器的行为。

问题

我最感兴趣的问题是，如果你不知道整个表达式，那么计算一个表达式的规则是什么？让我给你展示这个问题

我们将计算这个表达式

6*3+2*2+(2+3)

你可以用这种方式计算这个表达式

0: 6*3+2*2+(2+3)
1: 18+2*2+(2+3)
2: 18+4+(2+3)
3: 18+4+5
4: 27

你之所以能这样做，一个原因是，你从一开始就知道整个表达式。在这种情况下，你比计算器的情况要好。在时间 n，计算器只知道小于或等于 n 的表达式的所有位置。即使不知道整个表达式，它也开始计算。这是怎么做到的？这就是我的问题所在。

分析 

我开始分析我的计算器（TI-30Xa）的行为，并找出了一些要点

目前，我们只关心这些操作：+、-、*、/、(、)。

• 在输入数字时，显示的数字并不真正像一个数字。它更像一个字符串而不是一个数字。
• 按下数字键永远不会引起任何计算。
• 按下运算符键有时会引起计算。
• 每次按下运算符后，都可能发生计算。

现在，让我们仔细看看这些要点。

STRUMBER - 字符串/数字

当我们开始输入一个数字时，显示的数字行为像一个字符串。让我们在计算器上尝试输入 1024。我们开始按 #1、#0、#2 和 #5。发生了什么？这些数字被连接起来了。嗯，我想我们输错了数字。显示的是 1025 而不是 1024。没问题，我们按回退键，显示的是 102。数字 5 被删除了。现在按 #4，我们看到 1024。

我想你知道我说的“像字符串一样”是什么意思。

关键在于，只要显示数字没有用于计算，它就是一个字符串。

按下数字键永远不会引起任何计算

没什么可说的，试试吧。你可以输入任何你想要的数字，计算器永远不会计算任何东西。

按下运算符键有时会引起计算。

写下一些表达式，然后在计算器上输入。每当看到任何计算时，请在您的笔记中对应的位置记下“|”。

示例

6*2+|3+|4*2=|
1024/2*|(2+2)|-|1+|2=|
7+2*4*|0,5=|

我们看到了什么？

# ( 从不引起计算。目前，我们不知道这个键实际上做什么。

每当发生计算时，按下的键是以下之一：#+、#-、#*、#/、#) 或 #=

从这个角度来看，我们将它们都称为运算符。对这种不精确感到抱歉，因为从数学角度来看，#( 和 #) 并不是运算符。

目前，我们没有看到任何规则说明什么运算符在什么位置会引起计算。这比说“每当按下 #* 时就进行计算”要复杂得多。看看第一个表达式“...4*2=”，它没有引起计算，而在最后一个表达式“7+2*4*”中，最后一个 * 引起了计算。但到目前为止，我们有以下规则：

• 如果按下以下任一键：#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #- 或 #，则修改显示的数字。
• 如果按下以下任一键：#+ #- #* #/ 或 #)，则尝试计算。

计算系统

我是通过反复试验开发出这个系统的。我开始时有一个简单的想法，就是将数字和运算符推送到它们的堆栈上，然后尝试计算表达式。如果我看到系统失败了，我就会找出它不工作的原因并进行更改。经过一段时间和几杯茶，它变得越来越好。最终成功了。

如下所示

首先，每个运算符都有一个优先级

/ *    3
-    2
+    1

接下来，我们需要两个堆栈，一个用于存储数字，一个用于存储运算符。
此外，我们需要一个变量来存储最后输入的运算符的优先级（我们称之为 pol）。

最后，一个要计算的表达式：6+2*3-(2+3)=

要计算这个表达式，我们必须将这些工具与以下规则结合使用。

1. 如果按下数字键，则以相应的方式操作显示的数字。

- 如果按下运算符，则执行以下操作：
   1. 将显示的数字推送到数字堆栈。
   2. 尝试计算  
   3. 将按下的运算符推送到运算符堆栈。*
   4. 将 pol 设置为按下的运算符的优先级。

- 如果按下 # (：
   1. 将 pol 设置为 0。
   2. 将显示的数字设置为 0。
   3. 将按下的运算符推送到运算符堆栈。*

- 如果按下 # )：
   1. 尝试计算。
   2. 如果运算符堆栈顶部的运算符是“(”，则将其移除。*
  
*) 不要忘记 #( 和 #) 也是运算符。

尝试计算

这是整个系统中 J 最有趣的部分。计算本身非常简单，它遵循以下规则：

1. 从数字堆栈中取出两个最上面的数字。
2. 从运算符堆栈中取出最上面的运算符。
3. 进行计算并将结果推送到数字堆栈。

源代码可能看起来像这样：

var op:String = _opstack.pop().toString();
var p2:Number = Number(_numberStack.pop());
var p1:Number = Number(_numberStack.pop());

switch(op) {
    case "/":
        _numberStack.push( p1 / p2 );
        break;
    case "*":
        _numberStack.push( p1 * p2 );
        break;
    case "-":
        _numberStack.push( p1 - p2 );
        break;
    case "+":
        _numberStack.push( p1 + p2 );
        break;
} 

看看 p1 和 p2。P2 先被取出，因为它是第二个输入的数字，现在是堆栈顶部的数字。我们知道 10-2 != 2-10。

你认为我们已经拥有了所有必需的东西吗？不，还有最后一点。如果我们进行一次计算，我们不必只进行一次计算，而要尽可能多地进行计算。这就是我们关注 pol 的地方。如果当前按下的运算符的优先级小于或等于运算符堆栈顶部的运算符的优先级，我们就开始计算，并一直重复计算，只要 pol（最后输入的运算符的优先级）高于或等于运算符堆栈顶部的运算符的优先级。

源代码可能看起来像这样：

while ( 
        getPriority( nop ) <= getPriority(_opstack[_opstack.length - 1])
    && _pol >= getPriority(_opstack[_opstack.length - 1])
    && _opstack[_opstack.length - 1] != "("
) {
    ... calculation
}

就是这样！这是计算器最基本的系统。

当然，还有很多话要说，例如：

- 如果我们输入一个语法正确的表达式，这就能正常工作。但是对于这个呢？
3*2+((2-3)+4=

- 如果计算结果显示出来，我们不能通过按下数字键或逗号键来操作它。

关注点

你可能想知道我为什么要写这篇文章。去年我用 Actionscript 在 Flash 中写了一个计算器。但目前我正在学习 C++ 和 wxWidgets，为此，我需要一个小型项目来实现。这就是我重写这个计算器的原因。

此外，我认为让其他人了解它是如何工作的可能会很有趣，所以，我写了这篇文章。

如果你知道一种不同的方法来实现计算器，请告诉我。

历史 

2008-10-15 

我得到了一些差评。我读了这篇文章，意识到我把主要问题问错了。（计算器是否可以通过使用堆栈来实现）。而且我没有说明我将要在这个系列中做什么。内容变化不大，但希望现在有所改进。

2008-10-12  

首次发布。