题解 | #表达式求值#

最复杂的一集

class Solution {
  public:
    int solve(string s) {
        stack<char> sk;
        stack<int> res;
        int tmp;
        bool judge;//判断是否计算
        for (int i = 0; i < s.size();) {
            judge = false;

            if (!sk.empty()) {
                if (sk.top() == '*' && (s[i] >= 48 && s[i] <= 57)) { //计算
                    judge = true;
                    tmp = 0;
                    while (i < s.size() && s[i] >= 48 && s[i] <= 57) {
                        tmp = tmp * 10 + s[i] - 48;
                        i++;
                    }
                    tmp *= res.top();
                    res.pop();
                    res.push(tmp);
                    sk.pop();
                } else if (s[i] == ')') { //计算
                    judge = true;
                    while (sk.top() != '(') {
                        if (sk.top() == '-') {//'-'
                            tmp = res.top();
                            res.pop();
                            tmp = res.top() - tmp;
                        } else if (sk.top() == '+') { //'+'
                            tmp = res.top();
                            res.pop();
                            tmp = tmp + res.top();
                        } else { //'*'
                            tmp = res.top();
                            res.pop();
                            tmp = tmp * res.top();
                        }
                        res.pop();
                        res.push(tmp);
                        sk.pop();
                    }
                    sk.pop();
                    if (!sk.empty() && sk.top() == '*') { //'*('
                        tmp = res.top();
                        res.pop();
                        tmp = tmp * res.top();
                        res.pop();
                        res.push(tmp);
                        sk.pop();
                    }
                    i++;
                }
            }
            if (!judge) {//不计算，只压入栈
                if (s[i] >= 48 && s[i] <= 57) {
                    tmp = 0;
                    while (i < s.size() && s[i] >= 48 && s[i] <= 57) {
                        tmp = tmp * 10 + s[i] - 48;
                        i++;
                    }
                    if (!sk.empty() && sk.top() == '-') {
                        res.push(-tmp);
                        sk.pop();
                        sk.push('+');
                    } else res.push(tmp);
                } else {
                    sk.push(s[i]);
                    i++;
                }
            }
        }
        //最后的计算
        while (!sk.empty()) {
            if (sk.top() == '-') {//'-'
                tmp = res.top();
                res.pop();
                tmp = res.top() - tmp;
            } else if (sk.top() == '+') { //'+'
                tmp = res.top();
                res.pop();
                tmp = tmp + res.top();
            } else { //'*'
                tmp = res.top();
                res.pop();
                tmp = tmp * res.top();
            }
            res.pop();
            res.push(tmp);
            sk.pop();
        }
        return res.top();
    }
};

记录一个讨论区看到的题解，思路异常清楚

class Solution {
public:
    int solve(string s) {
        int res = 0; //用于返回当前字符串的计算结果
        stack<int> sum; //用于求和
        char sign = '+'; //记录前一个符号，初始化为+，因为可以看成当前字符串前先加0
        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; //用left记录最左括号位置，count记录左括号数，i当成右指针右移一格
                while(count > 0) { //最终目的是找到与最左括号匹配的右括号，类似于栈操作
                    if(s[i] == '(') count++;
                    else if(s[i] == ')') count--;
                    i++;
                }
                num = solve(s.substr(left + 1, i - left - 2)); //迭代计算括号内数值，注意不要包含最左最右括号，不然会死循环
                i--; //此时i是最右括号下一位，需要左移一位防止最右括号在字符串尾时发生越界从而使下面的判定失效
            }
            if(i == s.size() - 1 || s[i] == '+' || s[i] == '-' || s[i] == '*') { //对于字符串尾，或者加减乘，此时我们用的符号是上一次的，结算当前数字
                if(sign == '+') sum.push(num); //加法入栈
                else 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; //返回当前字符串计算结果
    }
};