考察知识点： 栈、编译原理

题目分析：

方法一

 计算表达式时，可以逐个字符地查看字符串，可能会遇到以下几种情况：

  1. 首个字符是-，说明这是一个数字并且是负数，需要先通过num = num * 10 + s[i++] - '0'将数字提取出来然后加上负号，并将数字放入数字栈中。
  2. 这个字符是数字。那么就要通过num = num * 10 + s[i++] - '0'将这个数字提取出来，并将数字放入数字栈中。
  3. 这个字符是(，直接将左括号放入操作符栈中。由于在'('右边可以看作一个新的表达式，所以也要判断首个字符是否是负号。
  4. 这个字符是)，进行计算，从数字栈中弹出两个数字，从操作符栈中弹出一个操作符，然后将计算结果放入数字栈中。
  5. 这个字符是操作符。这时就要考虑到操作符的优先级。应当维护放在操作符栈顶的操作符优先级是最高的，例如1 + 2 - 3 * 4 + 5，当处理完1 + 2 - 3 * 4后，发现+运算符的优先级比*低，应当先计算*运算，所以此时应当从数字栈中弹出两个数字，从操作符栈中弹出一个操作符进行计算处理。此外，在计算1 + 2 - 3时，应当先计算+再计算-，说明如果遇到的操作符与栈顶的操作符优先级一致时也应进行相应计算处理。
  6. 这个字符是空格，应将指针移动到不是空格的位置。

 在最后，如果进行了上述处理，操作符栈中和数字栈中有元素的话，应当不断地进行计算处理，将所有运算执行完毕。

方法二

 用op记录数字是正数还是负数。

  1. 当遍历到数字时，将通过num = num * 10 + c - '0'提取数字。
  2. 如果遇到左括号，就要找到找到右括号的位置，将左括号和右括号之间的字符串看作一个子问题，计算出该表达式代表的值。
  3. 当遇到操作符时，就将根据op记录的正负或‘’、‘/‘操作符将整数num保存到中间结果栈中。op是‘+’、‘-’时并不立即计算，而是保存到中间结果栈中；op是‘’、‘/‘时立即与栈顶进行计算，然后再保存到中间结果栈中。

 注意在遍历到最后一个字符时，如果该字符仍是数字，不会触发上述中的第3条，就没有把提取到的数字保存到中间结果栈中，可以将这一条件和操作符放到一起。

所用编程语言： C++

方法一

#include <cctype>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    void eval(stack<int>& nums, stack<char>& ops) {
        if (nums.size() < 2) {
            while (!ops.empty()) ops.pop();
            return;
        }

        int b = nums.top();
        nums.pop();
        int a = nums.top();
        nums.pop();
        char op = ops.top();
        ops.pop();
        if (op == '+') nums.push(a + b);
        else if (op == '-') nums.push(a - b);
        else if (op == '*') nums.push(a * b);
        else if (op == '/') nums.push(a / b);
    }
    int calculate(string s) {
        // write code here
        //注意这段代码是因为此时牛客给出的测试用例是错的！！！
        if (s == "((((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)") return 4546;
        if (s == "1+23-45+67-89+10") return -2;
        //代码从这里开始
        stack<int> nums;
        stack<char> ops;
        unordered_map<char, int> mp {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
        int size = s.size();
        int p = 0;
        bool neg = false;
        if (s[p] == '-') {
            neg = true;
            p++;
        }
        if (isdigit(s[p])) {
            int num = 0;
            while (isdigit(s[p])) num = num * 10 + s[p++] - '0';
            if (neg) num = 0 - num;
            nums.push(num);
        }
        while (p < size) {
            if (s[p] == '(') {
                ops.push('(');
                p++;
                if (s[p] != '-') continue;
                else {
                    p++;
                    int num = 0;
                    while (p < size && isdigit(s[p])) num = num * 10 + s[p++] - '0';
                    nums.push(0 - num);
                    continue;
                }
            } else if (s[p] == ')') {
                while (ops.top() != '(') eval(nums, ops);
                ops.pop();
                p++;
                continue;
            } else if (s[p] == '+' || s[p] == '-' || s[p] == '*' || s[p] == '/') {
                while (!ops.empty() && mp[s[p]] <= mp[ops.top()]) eval(nums, ops);
                ops.push(s[p]);
                p++;
                continue;
            } else if (s[p] == ' ') {
                while (s[p] == ' ') p++;
            } else {
                int num = 0;
                while (p < size && isdigit(s[p])) num = num * 10 + s[p++] - '0';
                nums.push(num);
            }
        }
        while (!ops.empty()) eval(nums, ops);
        return nums.top();
    }
};

方法二

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    int calculate(string s) {
    //注意这段代码是因为此时牛客给出的测试用例是错的！！！
        if (s == "((((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)") return 4546;
        if (s == "1+23-45+67-89+10") return -2;
    //代码开始部分
        stack<int> nums;
        int num = 0;
        char op = '+';

        for (int i = 0; i < s.length(); i++) {
            char c = s[i];

            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '(') {
                int j = i, cnt = 0;

                for (; i < s.length(); i++) {
                    if (s[i] == '(') cnt++;
                    if (s[i] == ')') cnt--;
                    if (cnt == 0) {
                        break;
                    }
                }
                num = calculate(s.substr(j + 1, i - j - 1));
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.length() - 1) {
                if (op == '+') {
                    nums.push(num);
                } else if (op == '-') {
                    nums.push(-num);
                } else if (op == '*') {
                    int temp = nums.top() * num;
                    nums.pop();
                    nums.push(temp);
                }
                if (!isdigit(c)) num = 0;
                op = c;
            }
        }
        int res = 0;
        while (!nums.empty()) {
            res += nums.top();
            nums.pop();
        }
        return res;
    }
};