模拟计算器（lc224)可扩展版 吐血整理

题目大意

以前我看到 “所爱隔山海，山海不可平”
当时我觉得 “海有舟可渡，山有路可行”
后来才发现 “山海皆可平，难平是人心”

本题是让你模拟一个计算器，但是本题只有+，-和括号，我们将此题扩展到带有*，/的版本。
以前模模糊糊记得写过这种类型的，大致思想就是用栈，但发现写的时候还是会漏洞百出，现在这里记录一下。

分析

先看本题吧，leetcode给出的官方题解很简洁，大致思想是：由于本题只有正负号，因此我只需要找出每个数字前的符号，然后一个sum累计求和即可，那么怎么找这个符号呢，它用了一个符号栈，栈中只存两个数（1，-1）,1代表当前符号是正号，-1代表是符号。算法起始忘栈中push一个1，然后遍历字符串并且维护一个sign值（1，-1）表示当前的符号，当遇到‘+’时，sign赋值为栈顶元素值（sign = stack.top()），遇到‘-’时，sign赋值为栈顶元素的相反数，这样就代表了下一个数字的符号，遇到数字就直接求和（根据sign决定加还是减），遇到括号要注意一下，若遇到左括号，需要将当前的sign值入栈（因为当前sign值代表了下一个数字的正负，如果下一个符号是括号，则说明括号中都应该是负号，如：“-（2+5）”），遇到右括号就出栈一个值。算法大体思想就是这样
这种思想写出来的代码很简洁，但是感觉还是不太好想。

leetcode官方题解代码

class Solution {
 public:
     int calculate(string s) {
         stack<int> ops;
         ops.push(1);
         int sign = 1;
 
         int ret = 0;
         int n = s.length();
         int i = 0;
         while (i < n) {
             if (s[i] == ' ') {
                 i++;
             } else if (s[i] == '+') {
                 sign = ops.top();
                 i++;
             } else if (s[i] == '-') {
                 sign = -ops.top();
                 i++;
             } else if (s[i] == '(') {
                 ops.push(sign);
                 i++;
             } else if (s[i] == ')') {
                 ops.pop();
                 i++;
             } else {
                 long num = 0;
                 while (i < n && s[i] >= '0' && s[i] <= '9') {
                     num = num * 10 + s[i] - '0';
                     i++;
                 }
                 ret += sign * num;
             }
         }
         return ret;
     }
 };

通用的计算器

下面介绍通用的计算器（包含加减乘除和括号的），目前有两种做法，一种是将中缀表达式转化为后缀表达式（逆波兰表达式），一种是用双栈。

首先，由于引入了乘除号，那么要定义优先级，乘除的优先级比加减要高，同时由于左括号也需要进栈，因此有可能也会判断左括号的优先级，简单分析一下，给由于左括号进栈后还没有运算数，因此遇到下一个运算符不应该直接运算，因此这里定义左括号的优先级比正负号低。但是比下文中定义的特殊字符‘#’，‘$’优先级高，否则会出问题。

对于逆波兰表达式，这种实际上就是后缀表达式，运算符号放在最后的一种表达式，为什么会出现这种表达式的原因是因为人类擅长中缀表达式，而计算机恰恰擅长后缀表达式。同时，后缀表达式没有符号的优先级和括号，因此不需要考虑那么多。后缀表达式一般用二叉树实现，后缀表达式的中序遍历（需要自己在遍历过程中加括号）就是中缀表达式，因此计算后缀表达式的值是非常容易的，只需要用一个栈存储运算数，遇到符号就取出两个数进行运算再压栈即可。那么中缀表达式如何转化为后缀表达式呢？这里需要借助两个栈，一个存运算数结点指针，一个存运算符结点指针。前面说了后缀表达式一般用二叉树来实现，因此栈中存入的元素是二叉树结点指针。

算法开始，遍历中缀表达式，往符号栈中加入一个优先级最低('#')的符号结点，在字符串末尾加入一个优先级次低的符号结点（‘$’）,这样，遍历的时候遇到数字就新建结点压入栈内，遇到符号就判断当前符号和栈顶符号的优先级，如果优先级大栈顶号的优先级，那么就入栈，否则一直出栈，出栈操作具体为：在运算数栈中取两个操作数结点指针，将出栈的运算符结点指针左右指针分别指向这两个操作数，然后将该节点压入运算数栈中去。遇到左括号就进栈，遇到右括号就出栈并进行相应操作直到左括号也出栈，最终运算数栈中的栈顶即为根节点指针。
对于这种方式，解决这个题太过繁琐了，但是这种逆波兰表达式我们需要要熟悉，有的题需要你转化成逆波兰表达式，这里代码很久之前写的了，找不太到了，先搁置。。。有空再补充一下

另外一种其实还是上面那种思想，可以直接双栈，一个存运算数，一个存符号，往符号栈中加入一个优先级最低('#')的符号，在字符串末尾加入一个优先级次低的符号（‘$’）（末尾加入字符的）。然后遍历表达式，遇到操作符就判断栈顶运算符的优先级是否大于等于当前运算符，如果大于等于，就先出栈并进行运算，否则就继续入栈，遇到左括号就入栈，遇到右括号就出栈直到左括号也出栈，最后数字栈栈顶就是结果。
有三个小细节

• 判断栈顶运算符优先级和当前符号优先级的时候必须用大于等于（>=),因为举个栗子：‘1-2+3’,正负号是同一优先级，如果不先运行前面的负号，其结果就变成了1-（2+3）=-4,可以模拟运行下，这是因为没有带上操作数的符号导致的。
• 初始时需要在数字栈中加入数字0，防止出现以负数开头的测试用例，如：-2+5，这时候遇到‘+’需要先计算‘-’号，但是数字栈中只有一个数字，这时候强行取两个数字就会报错，因此加一个0保险。
• 每遇到一次左括号要判断是否需要补充0，比如：“-25-(-32)”,可以模拟下，如果不在遇到左括号往栈里添0，就会出问题，少一个操作数，因此需要补充0，这里补充0的标准是判断括号后面的字符是否带有符号（‘+’， ‘-’），如果带有符号，则进行补充0的操作。但是由于某些测试用例很恶心，如"-2*( -3 +4)"这种，在左括号和符号之间有一些空格，因此这里还需要一个循环去判断遇到的第一个字符是否是符号（leetcode官方没有这种测试用例，是我自己发现的）。 上面陈述可能有一些混乱，可以结合代码看，我自己反复测试了很多用例，感觉下面这份代码应该没啥问题，感觉算是一个比较全面的加减乘除和带括号的计算器

 #include <iostream>
 #include<string>
 #include<stack>
 using namespace std;
 stack<int>number;
 stack<char>symbol;
 // 以前我看到 “所爱隔山海，山海不可平”
 // 当时我觉得 “海有舟可渡，山有路可行”
 // 后来才发现 “山海皆可平，难平是人心”
 //官方题解比较简洁，我写个复杂的双栈
 int getPriority(char ch) { // 可以扩展到加减乘除
     if (ch == '#') {
         return 0;
     }
     else if (ch == '$') {
         return 1;
     }
     else if (ch == '(') { // 这里可以定义左括号的优先级，也可以不用定义，若不定义的话需要判断栈顶字符不是左括号
         return 2;
     }
     if (ch == '+' || ch == '-') {
         return 3;
     }
     else {
         return 4;
     }
 }
 void cal() {
     char ch = symbol.top();symbol.pop();
     int a = number.top(); number.pop();
     int b = number.top(); number.pop();
     if (ch == '+') {
         number.push(a + b);
     }
     else if (ch == '-') {
         number.push(b - a);
     }
     else if (ch == '*') {
         number.push(a * b);
     }
     else {
         number.push(b / a);
     }
 }
 int calculate(string s) {
     int ret = 0;
     int last = 0;
     number.push(0); //防止出现-2这种
     symbol.push('#');  // 这个符号的作用主要是防止栈空和运算结束
     s += '$'; // 这个符号的作用是使运算结束，遇到这个符号，最终符号栈会一直出栈，直到遇到‘#’,这时候运算结束。
     for (int i = 0; i < s.size(); i++) {
         if (s[i] == ' ') {
             continue;
         }
         else if (s[i] <= '9' && s[i] >= '0') { // number
             int j = i;
             while (s[j] >= '0' && s[j] <= '9') {
                 j++;
             }
             string str = s.substr(i, j - i);
             i = j - 1;
             int cur = 0;
             for (char ch : str) {
                 cur *= 10;
                 cur += ch - '0';
             }
             number.push(cur);
         }
         else if (s[i] == ')') {
             while (symbol.top() != '(') {
                 cal();
             }
             symbol.pop();
         }
         else if (s[i] == '(') {
             symbol.push(s[i]);
             int j = i + 1; // 用来解决 "( -3 + 4) + (    -2 + 4)" 这种问题，leetcode测试用例没有这种例子。
             while (j < s.size() && s[j] == ' ') {
                 j++;
             }
             if (s[j] == '+' || s[j] == '-') {
                 number.push(0);
             }
         }
         else {  //symbol
             while (getPriority(symbol.top()) >= getPriority(s[i])) {
                 cal();
             }
             symbol.push(s[i]);
         }
     }
     return number.top();
 }

总结

这种题确实有点恶心,以前做过的，还是写不出来，而且要写到完美也只有不停的测试用例然后去改变，用了双栈，加入了‘#’，‘$’，而且需要补充0，遇到括号也需要判断是否补充0，有很多小细节。转化成后缀表达式的时候好像也需要补0操作，但是上面忘记说明了,突然感觉它俩思想是完全一样的啊，只是这种是吧值算了出来而已，哪个后缀表达式没有求值而已！