题解 | 表达式求值

个人觉得写这道题的关键在于理解数学公式计算时的思维过程，

首先就算是看运算符的优先级，我使用了哈希表来实现，*的优先级为2，+法于-法为1.

然后就得弄清楚什么时候计算：

1.有括号时，先算括号中的，

1.可以从输入的第一个左括号算起，当遇到右括号时计算出括号中的总值.

2.如果不知道具体该怎么样运算，可以先用一个calcul函数替代(只要知道这个函数是将结果存储在num.top上即可)，等后续再 补充.

2.当一个运算符的下一个运算符优先级不大于他自身时(可以将这个运算符和他旁边的两个数算出)，这又要分2种情况：

1.这个运算符的下一个运算符不大于他（对应solve函数中的if (map[op.top()] >= map[i])）

这种情况下直接在solve函数中算出即可，如果下一个的优先级大于他，则先存入符号栈中，等到后续再统一计算。

2.这个运算符的上一个不大于他（对于calcul中的if (map[c] >= map[op.top()])的else块）

这种情况负责处理上一种情况剩下的数据，会将优先级高的符号消去，保留同级的符号.最后实现运算.

由上述分析，得：

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int select(int x1, int x2, char op) {
        switch (op) {
            case '+':
                return x1 + x2;
                break;
            case '-':
                return x1 - x2;
                break;
            case '*':
                return x1 * x2;
                break;

        }
        return 0;
    }//计算.


    void calcul(stack<int>& num, stack<char>& op) {
        unordered_map<char, int> map = {
            {'+', 1},
            {'-', 1},
            {'*', 2}
        };
        if (op.empty()) return ;
        if (num.size() < 2) return;
        char c = op.top();




        if (op.size() > 1) {
            op.pop();
            if (op.top() != '(') {
                if (map[c] >= map[op.top()]) {
                    int x2 = num.top();
                    num.pop();
                    int x1 = num.top();
                    num.pop();
                    num.push(select(x1, x2, c));
                } else {

                    int x2 = num.top();
                    num.pop();
                    int x1 = num.top();
                    num.pop();
                    int x3 = num.top();
                    num.pop();
                    num.push(select(x3, x1, op.top()));
                    op.pop();
                    op.push(c);
                    num.push(x2);

                }//如果进入else代表op.top()一定是'*'，所以先只计算优先级大的乘法，将优先级小的再放回去.
            } else {
                int x2 = num.top();
                num.pop();
                int x1 = num.top();
                num.pop();
                num.push(select(x1, x2, c));
            }//如果去掉一个符号是左括号，代表只有1个运算符号

        }






        else {
            int x2 = num.top();
            num.pop();
            int x1 = num.top();
            num.pop();
            num.push(select(x1, x2, c));
            op.pop();
        }


    }
    int solve(string s) {
        unordered_map<char, int> map = {
            {'+', 1},
            {'-', 1},
            {'*', 2}
        };
        stack<int> num;
        stack<char> op;
        int now = 0;
        for (char i : s) {
            if (i >= '0' && i <= '9') {
                now = now * 10 + i - '0';

            } else {
                if (now != 0) {
                    num.push(now);
                    now = 0;
                }

                //处理符号
                if (i == '(') {
                    op.push(i);
                } else if (i == ')') {
                    while (op.top() != '(') {

                        calcul(num, op); //calcul中要记得消去左括号

                    }
                    op.pop();
                } else {



                    if (op.empty() || num.size() < 2) {
                        op.push(i);
                    } else {

                        if (map[op.top()] >= map[i]) {
                            int x2 = num.top();
                            num.pop();
                            int x1 = num.top();
                            num.pop();
                            num.push(select(x1,x2,op.top()));
                            op.pop();
                            op.push(i);

                        } else {
                            op.push(i);
                        }

                    }

                }

            }
        }

        if (now != 0) {
            num.push(now);
            now = 0;
        }


        while (!op.empty()) {

            calcul(num, op);

        }
        return num.top();

    }
};