基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

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

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

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

提示：

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

思路：用栈保存左括号左边的符号值，对于每个数字，相当于做了去括号的操作，计算出该数字实际表示的正负。最后，总和直接加上该数字就行

    int calculate(string s) {
        int n = s.size();
        stack<int> st;
        st.push(1);
        int sign = 1;
        long long res = 0;
        int i = 0;
        while (i < n) {
            if (s[i] == ' ') {
                i++;
            } else if (s[i] == '+') {
                sign = st.top();
                i++;
            } else if (s[i] == '-') {
                sign = -st.top();
                i++;
            } else if (s[i] == '(') {
                st.push(sign);
                i++;
            } else if (s[i] == ')') {
                st.pop();
                i++;
            } else {
                long long num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                res += sign * num;
            }
        }
        return res;
    }