题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        int res = 0;
        stack<int> sum;
        char sign = '+';
        int num = 0;
        for(int i= 0; i < s.size();i++) {
            if(s[i] >= '0' && s[i] <= '9') {
                num = 10 * num + s[i] - '0';
            }

            if(s[i] == '(') {
                int left = i++,count = 1;
                while(count > 0) {
                    if(s[i] == '(') count++;
                    if(s[i] == ')') count--;
                    i++;
                }
                num = solve(s.substr(left +1, i - left -2));
                i--;
            }
            if(i == s.size() - 1 || s[i] == '+' || s[i] == '-' || s[i] == '*') {
                if(sign == '+') sum.push(num);
                if(sign == '-') sum.push(-num);
                else if(sign == '*') sum.top() *= num;
                sign = s[i];
                num = 0;
            }
        }
        while(!sum.empty()) {
            res += sum.top();
            sum.pop();
        }
        return res;
    }
};

思路 辅助栈 + 递归算法

先遍历字符串，重点是用sign记录上一次的符号，碰到符号后，判断上一次的符号是什么，如果是加减就压入对应正负数进入栈，如果是乘法，就将上次的先计算记过stack.top()的数据 * 当前的遍历字符串。
+ - 很好解决，判断符号，然后向栈中压入 一个正负数，如何保证*优先级，压入栈中的数据都是最后在取出统一相加，得出运算结果，所以，，*的数据在压入数据之前就计算好，遇到*，
遇到括号，使用str.substr分割字符串，分割得到括号内的数据，将字符串传入revose（）函数，递归。