使用栈实现一个简单的计算器

目标

向计算机输入完整的四则运算表达式，计算机输出计算结果，并且在此基础上适当的加强程序的健壮性，让程序具有识别非法表达式以及一定程度上整理表达式的能力，例如：

输入： (56-23)/8-4 ，输出： 0.125

输入： 34+p(u89-12.3)k/3 ，输出： 59.566667

输入： (8*(7-4) ，输出： 输入有误

基本原理

关于 Stack

Stack 是数据结构中最基础最简单的一种（也是我才学会的两种之一），它的特点是 First In Last Out ，先进后出，就像放在架子上的盘子，想要取出下面的盘子，必须拿出上面的盘子。对于一个Stack` ，我们有三个基本操作：

• push ：将元素压入栈顶，可以类比为将盘子放到架子上。
• pop ：将栈顶元素弹出，可以类比为取下架子上的第一个盘子。
• top ：返回栈顶元素。

在计算机中， Stack 有两种最主要的实现方法， LinkedStack 和 ArrayStack ，前者基于单链表存储，后者基于数组存储。基于数组存储的 Stack 较为方便理解，所有元素存储在数组中，数组存储的最后一个元素即为 Stack 的栈顶元素，压入新元素时自然而然存储在数组中前一个栈顶元素下标+1的位置。基于单链表存储的 Stack 相对来说更难理解。

简单介绍一下单链表的原理，所有元素分别存储在各自的节点中，这个节点同时还存储了另一个节点的地址。这样的话，当获取了一个节点，在获取了所存储的元素的值的同时，还获得了另一个节点的地址，而获得了另一个节点的地址，就相当于获得了另一个节点所存储的元素的值以及另一个节点存储的又一个节点的地址。如此循环往复，每个节点存储下一个节点的地址，找到一个节点就能依次找到所有之后的节点，所有节点像一根线一样穿在一起，所以称为单链表。

知道了单链表的原理以后，回到 Stack 的实现，我们只需要构造一个节点，专门用于存储栈顶元素所在的节点地址，将这个节点称为 topNode ，每压入一个新的元素，便构造一个新的节点，存储新元素以及 topNode 所存储的原栈顶元素所在的节点地址，再修改 topNode 使其存储新的栈顶元素的节点地址。当要弹出栈顶元素时，修改 topNode 令其指向栈顶元素的下一个元素所在节点的地址（该地址通过栈顶元素获得），使该地址所在节点的元素成为新的栈顶元素，与此同时原先栈顶元素由于再没有指向它的变量，在某些语言中就会被系统当作垃圾自动回收内存。

两种 Stack 在实际应用中也稍有区别， ArrayStack 的大小取决于数组的大小，调整复杂，且在声明初始就已经分配了内存，不灵活，但是可以通过数组下标迅速访问某一个元素。 LinkedStack 的大小不固定，可以调整，在插入数据项时动态的分配内存，自由度大，但是若要访问某一个元素必须从栈顶元素开始遍历。

关于 Calculator

Calculator 的基本原理是将中缀表达式转换为后缀表达式进行求解。例如， 1+2*(4-3) 这样一个符合我们阅读习惯的表达式就是中缀表达式，而将该表达式转换为后缀表达式即为： 1243-*+ ，在计算机系统中，从左到右读取后缀表达式，当遇到操作符时，取出操作符和操作符前的两个操作数，计算后将得到的结果放回原位，继续读取。以上面的表达式为例，读取到 - 号的时候，取出 43- ，计算 4-3 ，得到 1 放回原位，表达式变为 121*+ ，读取到 * 号的时候，取出 21* ，计算 2*1 ，得到 2 放回原位，表达式变为 12+ ，读取到 + 号的时候，取出 12+ ，计算 1+2 ，得到 3 放回原位，此时只剩下 3 ，即为表达式的结果。

简单的介绍了计算后缀表达式的原理，下一步需要将中缀表达式转换为后缀表达式，这里有一套方法直接给出：

创建两个Stack，分别存储操作符和操作数，从左到右扫描中缀表达式，若为操作数直接压入操作数栈，若为操作符，则与操作符栈顶元素进行优先级的比较，

若大于，则压入操作符栈继续扫描；

若等于，退出栈顶元素继续扫描（只有一种情况会等于，两个操作符分别是(，)，这时候操作符优先级相等）；

若小于，从操作符栈退出栈顶元素，并从操作数栈退出两个元素，进行计算后压入操作数栈，并继续用读取到的操作符与操作符栈中的下一个操作符进行比较。这套方法结束后，操作数栈中的元素即为表达式的结果。

实现思路

由于相对来说，我更熟悉 Java 语言，所以我选择使用 Java 语言来实现 Calculator ，在 Stack 的选择上，由于给定的表达式长度唯一，使用 ArrayStack 也无需担心无法灵活调整大小的困难，故而 ArrayStack 和 LinkedStack 在这个实例中效果几乎是等效的，选取自己熟悉的 Stack 类型即可。我在这里选择的是 LinkedStack 。

我们需要创建两个类，一个 Stack 类实现创建 Stack 以及 Stack 的基本操作，一个 Calculator 类负责对输入的字符串进行计算。

将表达式输入到程序中以后，首先第一步先格式化表达式，整理表达式使其不含非法字符，格式化表达式以后对表达式进行判别，如果表达式非法，直接返回不再进行后续操作，如果表达式合法，开始从左到右扫描表达式，按照之前介绍的方法将中缀表达式转换为后缀表达式并进行求值，最后返回计算结果。

遇到的困难

如何终止运算

为了美观以及符合日常习惯，我们需要在表达式的末尾加上一个 = 号，当扫描到这个 = 号的时候，即终止运算。但是之前给出的计算中缀表达式的方法并不包括如何处理终止符的方法，在这里我们改进那个方法，使其能够处理终止符。

我们在开始操作前先向操作符栈压入一个 = 号，当扫描到倒数第二个操作符时，此时理论上计算完后操作数栈的顶部已经是计算式结果了，并且操作符栈的除之前压入的 = 号外再无第二个操作符，此时再向下扫描得到末尾的 = 号，继续进行与操作符栈栈顶进行比较的操作，两者都是 = 号，即判断为运算结束，此时返回操作数栈栈顶作为结果输出到控制台。

如何识别并处理非法表达式

首先我们观察几个典型的非法表达式，

34+p(u89-12.3)k/3 ， 89.5*749*+25) ， (8*(7-4) ， 65*(72+98)(70-45) ， 6* ， )5+3( ， 3+(2..5*4)/2.

不难看出非法表达式的几个错误：

1. 含有非法字符
2. 括号数量或顺序不匹配
3. 小数点数量异常
4. 缺少操作符或操作数

这些错误又可以分为两类，可以还原成合法表达式的错误以及不可以还原的错误，分析完非法表达式的问题，我们要做的就是将我们可以处理的非法表达式还原成合法表达式，不能处理的返回输入异常。例如 6* 我们便无法还原，我们无法揣测用户在乘号后面还想要输入的内容。 34+p(u89-12.3)k/3 我们就可以还原，只要把非法字符删除就可以得到一个合法表达式。

含有非法字符以及小数点数量异常是我们能处理的两类错误，归结起来这两类错误本质都是用户在已经输入了合法表达式的基础上多输入了额外的字符。处理非法字符较为简单，从左到右扫描表达式，遇到不是操作符或者操作数的字符就将其从字符串中删除，这里我使用了 Java 中 String 类的 substring 方法将表达式以非法字符为分界拆分为两个子串，再将子串拼接到一起，实现删除非法字符的功能。这里用到两个函数， isNum 和 isOperator ，判断给定的字符是否属于操作数以及操作符，具体实现是十分简单的 boolean 函数，不再赘述。

而小数点数量异常分为两类，一类是在浮点数中输入了过多的小数点，例如2…5，另一类是在整形数的结尾误输入了小数点，例如2.这样的，我们可以通过它们的规律来对这类错误进行处理，第一类的特点是在扫描到一个小数点后下一个扫描到的字符还是小数点，第二类的特点是在扫描到一个小数点后下一个扫描到的字符不是数字字符而是操作符字符。

所以非法字符错误和小数点错误最终处理方法都是删除特定的字符，只是判断条件不同，下面给出关键代码：

for(int i = 0; i < arithmetic.length(); i++){
    if(!isNum(arithmetic.charAt(i)) && !isOperator(arithmetic.charAt(i))){
        str = arithmetic.substring(0,i) + arithmetic.substring(i + 1);
        break;
    }
    if(arithmetic.charAt(i) == '.' && arithmetic.charAt(i + 1) == '.'){
        str = arithmetic.substring(0,i) + arithmetic.substring(i + 1);
        break;
    }
    if(arithmetic.charAt(i) == '.' && isOperator(arithmetic.charAt(i + 1))){
        str = arithmetic.substring(0,i) + arithmetic.substring(i + 1);
        break;
    }
}

解决了能处理的错误，剩下不能处理的错误我们需要找出其通性进行判断，主要有三个判断的条件：

第一：括号数量不匹配，例如 (8*(7-4) ，只需要写一个函数，扫描表达式分别统计左右括号数目即可。

第二：括号顺序不匹配，例如 )5+3( ，要判断这个条件需要扫描表达式，并记下左右括号每次出现的位置，最后比较是否有第n个右括号在第n个左括号之前的情况，在一个合法的表达式中，第n个左括号总是位于第n个右括号之前，可与第一个判断条件合并到一个函数中进行判断。

第三：运算符数是否是运算数数-1，在合法表达式中，这条关系总是成立，通过这个条件的判断，可以把缺省操作符或者操作数的非法表达式检测出来。这个判断很简单，只需要遍历表达式统计数目即可。

判断括号匹配的方法：

private boolean isBracketsPair(){
    int[] leftBracketPosition = new int[arithmetic.length()],
            rightBracketPosition = new int[arithmetic.length()];
    int numOfLeftBrackets = 0, numOfRightBrackets = 0;
    for(int i = 0; i < arithmetic.length(); i++){
        if(arithmetic.charAt(i) == '('){
            leftBracketPosition[numOfLeftBrackets] = i;
            numOfLeftBrackets++;
        }
        if(arithmetic.charAt(i) == ')'){
            rightBracketPosition[numOfRightBrackets] = i;
            numOfRightBrackets++;
        }
    }
    for(int i = 0; i < arithmetic.length(); i++){
        if (leftBracketPosition[i] > rightBracketPosition[i])
            return false;
    }
    return numOfLeftBrackets == numOfRightBrackets;
}

至此非法表达式的识别与处理就结束了，通过这几个方法，可以处理绝大部分的非法表达式，如果有不能处理的，请务必告诉我，方便继续改进。

如何将输入的表达式字符串处理为浮点型数据

我们在输入表达式的时候将表达式存储在了一个 String 类型的变量中，这也就意味着，操作符以字符的形式存储了，操作数也以字符的形式存储了，存储的其实是它们的 ASCII 码值，而不是字面值。以0为例，0对应的字符的 ASCII 码值为48，所以当我们从表达式中读取数字的时候，读取到的其实是它们的 ASCII 码，如果不进行处理，我们不可能用 ASCII 码进行计算，所以这里涉及到一个问题就是如何将以 ASCII 码值形式存储的数字字符转换浮点型的字面值。

还有第二个问题，如果每个数都是10以内的整数，很方便就能进行转换，但是实际上这是不存在的情况，计算式中会有大数，也会有浮点数。以12.5为例，它存储在 String 中并不是一个值，而是四个值，分别是1，2，小数点，5对应的 ASCII 码，所以第二个问题就是如何连续读取n个组成一个数字的字符并将它们转换为浮点数。

解决了第二个问题，也就解决了第一个问题，我们将第二个问题分为两个小问题来进行解决。首先解决将操作数对应的 ASCII 码值转换为字面值的问题，我们只需要将 ASCII 码的数减去48即为字面值。这个问题十分简单，但解决了这个问题后，我们的问题就变成了如何将n个顺序排列的浮点数以个十百千万的位数顺序组合成一个新的浮点数。

接下来给出完整解决思路，我们从左到右扫描表达式，当扫描到代表数字的字符时，将该字符转换为浮点型字面值并赋给中间变量，然后继续读取下一位，如果下一位还是数字，先转换成浮点型字面值，然后将中间变量扩大10倍，加上新一位的字面值，以此类推。

以123为例，首先扫描到1，对应的 ASCII 码为49，转换为字面值1，赋给中间变量，此时中间变量值为1；然后扫描到2，转换为字面值后，先将中间变量扩大10倍变成10，再加上2变成12；然后扫描到3，中间变量扩大10倍，加上3变成123，得到三个字符所代表的字面值。

但是形同123这样的数只是最基本的整数，以整数为例介绍算法较为简单，针对带小数部分的浮点数，还需要修改我们的步骤。我想到的是利用浮点数只是小数位数不同的特点，先忽略小数点，将浮点数的整数部分和小数部分一起组合为一个数，再根据小数点后有几位数对组合成的数进行倍数的放缩，这样便可以达到读取带有小数部分的浮点数的目的。

以123.45为例，前三位正常扫描，扫描到小数点的时候，进行标记，这个标记的含义代表了是否读取到小数点。然后继续读取后面的浮点数，每读取到一位浮点数，并且检测到已经读取到小数点的标记，则将放缩系数扩大10倍，最后当完全读取完毕，我们获得了一个浮点数12345，一个放缩系数100，两者相除得到123.45，成功获取到这五个字符所代表的字面值。

下面给出具体实现代码：

int countDecimalPlaces = 1;
boolean passDecimalPoint = false;
double temp = 0;

if(isNum(arithmetic.charAt(i))){
    do {
        if(passDecimalPoint)
            countDecimalPlaces *= 10;
        if(arithmetic.charAt(i) == '.') {
            passDecimalPoint = true;
            i++;
            continue;
        }
        temp = temp * 10 + ASCIINumToInt(arithmetic.charAt(i));
        i++;
    }
    while(isNum(arithmetic.charAt(i)));
    temp /= countDecimalPlaces;
    countDecimalPlaces = 1;
    passDecimalPoint = false;
  	temp = 0;
    i--;
}

如何判断操作符的优先级

在将中缀表达式转换为后缀表达式求值的过程中我们需要判断操作符的优先级然后根据判断结果进行不同的操作，我的方法是使用一个二维数组存储操作符的优先级：

int[][] operatorRelationship = {{'+',3,2},
                                {'-',3,2},
                                {'*',5,4},
                                {'/',5,4},
                                {'(',1,6},
                                {')',6,1},
                                {'=',0,0}};

介绍一下二维数组的含义，二维数组的第一列存储了操作符，第二列存储了操作符的栈内优先级，第三列存储了操作符的扫描优先级。简单解释一下栈内优先级和扫描优先级，扫描到的新操作符与栈顶操作符进行优先级对比时，扫描到的新操作符使用扫描优先级去对比栈顶操作符的栈内优先级，例如假设当前操作符栈内元素为 + ，扫描到下一个操作符为 - ，使用 - 的扫描优先级3去对比 + 的栈内优先级2，得到大于的结果，所以将 - 号压入操作符栈继续扫描。只需要遍历二维数组的第一列，发现匹配的操作符时，返回指定的优先级即可进行对比。需要注意的是在遍历二维数组之前必须将表达式格式化保证没有非法字符，否则可能会引起空指针异常。

存在的问题

之所以说这是一个粗暴的实现是有原因的，如果使用 Java 和 C++ 的标准 Stack 类，可以指定 Stack 所存储的类型，分别对操作符和操作数使用不同类型的 Stack 进行存储，就避免了将字符串转换为浮点型字面值的问题。这个问题主要还是源自于自身技术的欠缺，将来修改了 Stack 类的实现后再对这个问题进行弥补。