224. Basic Calculator

O(n) time
简化版的通用解法

class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) {
        char op = '+';
        long n = s.size(), num = 0, res = 0;
        for (; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
            } else if (c != ' ') {
                res += (44 - op) * num; // 因为没有*/所以不需要curRes来进行局部运算，直接用res累加即可
                op = c;
                num = 0;
                if (c == ')') break;
            }
        }
        return res;
    }
};

class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) {
        char op = '+';
        long n = s.size(), num = 0, res = 0;
        for (; i < n && op != ')'; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
                --i; // 因为最后循环终止条件是op != ')'所以当op为')'时i已经指向下一个符号，所以需要回退一个
            } else if (c != ' ') {
                res += (44 - op) * num; // 因为没有*/所以不需要curRes来进行局部运算，直接用res累加即可
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

因为只有加减法，维护两个栈，一个放当前的『和』，一个放加减法（1和-1）

class Solution {
public:
    int calculate(string s) {
        s += ' '; // padding
        stack<int> operands, operators;
        long sign(1), res(0), num(0);
        for (auto &&c : s) {
            if (isdigit(c)) {
                num = num * 10 + c - '0'; // 用long防止溢出
            } else {
                res += sign * num;
                num = 0;
                switch (c) {
                    case '+': sign = 1; break;
                    case '-': sign = -1; break;
                    case '(': {
                        operands.push(res);
                        operators.push(sign);
                        res = 0; // 开始括号内的新计算所以reset两个变量res和sign
                        sign = 1;
                    }
                    break;
                    case ')': {
                        res = operands.top() + operators.top() * res;
                        operands.pop();
                        operators.pop();
                    }
                    break;
                    default: break;
                }
            }
        }
        return res;
    }
};