【LeetCode】224. 基本计算器

括号展开 + 栈

核心是利用栈击穿括号，将符号转变为没有括号的样子。

栈顶保留括号前符号，加号括号内符号不变，减号括号内符号反转。

代码

class Solution {
public:
    int calculate(string s) {
        stack<char> st; // 存储正负号
        int ans = 0, num = 0, op = 1;
        st.push(op);

        for (char c : s) {
            if (c == ' ') continue;
            else if (c >= '0') num = num * 10 - '0' + c;
            else {
                ans += op * num;
                num = 0;

                if (c == '+') op = st.top();
                else if (c == '-') op = -st.top();
                else if (c == '(') st.push(op); // 将括号前符号放入栈顶
                else st.pop();
            }
        }

        return ans + op * num;
    }
};