772. Basic Calculator III

https://leetcode.com/problems/basic-calculator-iii/

Evaluate 由+-/()数字构成的数学表达式。有nested括号且代表优先级，用stack或recursion。分别用两个stack nums和ops存当前结果和操作符。先不考虑括号，a+b*c时不能直接算a+b，而应该把a b c都压进nums中直到结束再从stack开始eval b*c，即让b和c从nums出栈和ops.top做操作后结果入nums。因此用判断当前字符所代表的操作符是否高于栈顶（同时栈顶不能是‘(’），不高就不断对stack做eval。接着对括号进行处理，每次遇到(把(压进ops中，遇到)则iterative把该括号的（即'('前）都处理完。为了应对负数，在(后和nums为空时遇到-在nums里压入0。

class Solution {
public:
    int calculate(string s) {
        stack<long> nums;
        stack<char> ops;
        const auto higher = [](char a, char b) {
            if ((a == '*' || a == '/') && (b == '+' || b == '-')) return true;
            return false;
        };
        const auto op = [&]() {
            const auto b = nums.top(); nums.pop();
            const auto a = nums.top(); nums.pop();
            const auto o = ops.top(); ops.pop();
            switch (o) {
                case '+':
                    nums.push(a + b);
                    break;
                case '-':
                    nums.push(a - b);
                    break;
                case '*':
                    nums.push(a * b);
                    break;
                case '/':
                    nums.push(a / b);
                    break;
            }
        };
        long num = 0;
        for (int i = 0; i < s.length(); ++i) {
            auto c = s[i];
            if (isdigit(c)) {
                num = c - '0';
                while (i + 1 < s.length() && isdigit(s[i + 1])) {
                    num = num * 10 + (s[i + 1] - '0');
                    ++i;
                }
                nums.push(num);
                num = 0;
            } else if (c == '(') {
                ops.push(c);
                if (s[i + 1] == '-') {
                    nums.push(0);
                    ++i;
                    ops.push('-');
                }
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                if (c == '-' && nums.empty()) {
                    nums.push(0);
                    ops.push(c);
                    continue;
                }
                while (!ops.empty() && ops.top() != '(' && !higher(c, ops.top())) {
                    op();
                }
                ops.push(c);
            } else if (c == ')') {
                while (!ops.empty() && ops.top() != '(') {
                    op();
                }
                ops.pop();
            }
        } 
        while (!ops.empty()) {
            op();
        }
        return nums.top();
    }
};