题解 | #表达式求值#

实现 加 减 乘 和 括号 计算

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        int ans = 0;   // 最终结果
        stack<int> sums; // 记录中间值
        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; // left左括号位置， count括号深度
                while (count > 0) {  // 括号未完全匹配，完全匹配时为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 =='+') sums.push(num);  // 加法入栈 
                else if (sign == '-') sums.push(-num);  // 减法相当于加负数
                else if (sign == '*') sums.top() *= num;  // 乘法与栈顶相乘
                sign = s[i];  // 更新符号
                num = 0;  // 重置当前数
            }
        }
        while (!sums.empty()) { // 将栈内所有数字相加
            ans += sums.top();
            sums.pop();
        }
        return ans;  // 返回当前字符串计算结果
    } 
};