实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式

Solution

参考：@负雪明烛

重点：

• 本题目只有 "+", "-" 运算，没有 "*" , "/" 运算，因此少了不同运算符优先级的比较；
• 遇到小括号，应该先算括号里面的表达式；

操作的步骤是：

• 如果当前是数字，那么更新计算当前数字；
• 如果当前是操作符+或者-，那么需要更新计算当前计算的结果 res，并把当前数字 num 设为 0，sign 设为正负，重新开始；
• 如果当前是 ( ，那么说明遇到了右边的表达式，而后面的小括号里的内容需要优先计算，所以要把 res，sign 进栈，更新 res 和 sign 为新的开始；
• 如果当前是 ) ，那么说明右边的表达式结束，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个式子的结果；
• 最后，当所有数字结束的时候，需要把最后的一个 num 也更新到 res 中。

class Solution {
public:
    int calculate(string s) {
        int res = 0, num = 0, sign = 1;
        int n = s.size();
        stack<int> st;
        for (const char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                res += sign * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                st.push(res);
                st.push(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res += sign * num;
                num = 0;
                res *= st.top(); st.pop(); // 符号出栈
                res += st.top(); st.pop(); // 数字出栈
            }
        }
        res += sign * num;
        return res;
    }
};