Description

给定一个长度为\(n\)的表达式字符串\(s\)，里面包含：' '、[0-9]、[+-()]。求出表达式的最终结果。

Constraints

\(1 \le n \le 3 \times 10^5\)

Solution

使用递归下降即可。

expression   -> term   (('+' | '-') term)*
term         -> factor (('*' | '/') factor)*
factor       -> NUMBER | '(' expression ')'

总之对照上面的表复刻一下就好了，这里也顺便写了乘除法（下取整）。

为了代码整洁，这里需要抽象一个扫描控制器ctl，使得读取任意字符前都过滤掉空格。

Code

class Solution {
public:

    struct {
        string s;
        int pos;

        void skip() { while(s[pos] == ' ') pos++; }
        char peek() { return skip(), s[pos]; }
        char pop() { return skip(), s[pos++]; }
        bool accept(std::integral auto ...cs)
            { return ((peek() == cs) || ...); }
        bool accept(std::invocable<char> auto ...conds)
            { return (conds(peek()) || ...); }
    } ctl;

    int calculate(string s) {
        ctl.s = std::move(s);
        ctl.pos = 0;
        return expression();
    }

    int expression() {
        auto ans = term();
        while(ctl.accept('+', '-')) {
            if(ctl.pop() == '+') ans += term();
            else ans -= term();
        }
        return ans;
    }

    int term() {
        auto ans = factor();
        while(ctl.accept('*', '/')) {
            if(ctl.pop() == '*') ans *= factor();
            else ans /= factor();
        }
        return ans;
    }

    int factor() {
        auto ans = number();
        while(ctl.accept('(')) {
            ctl.pop();
            ans += expression();
            ctl.pop();
        }
        return ans;
    }

    int number() {
        int ans = 0;
        while(ctl.accept(::isdigit)) {
            auto c = ctl.pop();
            ans = ans*10 + (c - '0');
        }
        return ans;
    }
};

LeetCode-224 Basic Calculator