LeetCode-736 Parse Lisp Expression

Description

给定一段简化的Lisp表达式\(expression\)，返回其计算结果。

规则有点长，需要实现let、add、multi和有作用域范围的变量，具体请看原文。

Constraints

\(1 \le expression.length \le 2000\)

Solution

和224相同思路，但是本题多了变量和作用域。

其实简化Lisp的定义比一个计算器还简单：

e -> NUM | v | (let (v e)+ e) | (add e e) | (multi e e)
v: [a-z][a-z0-9]*
NUM: [+-]?[0-9]+

既然有作用域，那就模仿栈结构搞一个存放上下文信息的数据结构。不过落地到实现上，不建议使用std::stack，因为没有迭代器（需要按顺序访问外部作用域）；也不建议使用std::vector，引用会随扩容而失效；因此用了std::deque。

实现上令我不太满意的是let函数。像(let v e v)这种情况不好处理，原因是这里ctl是抽象成流设备的（我的想法是不要回头看），解决方法是向前检测')'，从而得知v其实是一个e，因此修正为合法的(let v e e)。就是写起来有点样衰。

另外，获取token前就不要无条件吞空格了，不然变量名v和数字NUM不好区分。所以这里区分检查用的first_accept()和处理过程中使用的accept()。

Code

class Solution {
public:
    struct {
        string s;
        int pos;
        char peek() { return s[pos]; }
        char pop() { return s[pos++]; }
        void pop(size_t step) { pos += step; }
        void eat(char c = ' ') { while(peek() == c) pop(); }
        bool _accept(char c) { return peek() == c; }
        bool _accept(invocable<char> auto cond) { return cond(peek()); }
        bool accept(auto ...all) { return (_accept(all) || ...); }
        bool first_accept(auto ...all) { return eat(), accept(all...); }
    } ctl;

    auto defer(auto f) {
        return shared_ptr<void>(nullptr, std::move(f));
    }

    using Int = long long;
    using Symbol_table = deque<unordered_map<string, Int>>;
    Symbol_table symbols;

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

    // e -> NUM | v | (let (v e)+ e) | (add e e) | (multi e e)
    Int expression() {
        if(auto num = number()) return *num;
        if(auto var = variant()) return *var;

        ctl.pop(); // (
        auto _ = defer([&](...) { ctl.pop(); }); // )

        switch(ctl.peek()) {
            case 'l': return ctl.pop(3), let();
            case 'a': return ctl.pop(3), expression() + expression();
            case 'm': return ctl.pop(5), expression() * expression();
        }
        return {};
    }

    optional<Int> number() {
        if(!ctl.first_accept(::isdigit, '-', '+')) return {};
        Int ans = 0;
        bool negative = ctl.accept('-', '+') && ctl.pop() == '-';
        while(ctl.accept(::isdigit)) {
            ans = ans * 10 + (ctl.pop() - '0');
        }
        return negative ? -ans : ans;
    }

    optional<Int> variant() {
        if(!ctl.first_accept(::isalpha)) return {};
        return variant_value(variant_name());
    }

    Int let() {
        auto &local = symbols.emplace_front();
        auto _ = defer([&](...) { symbols.pop_front(); });
        // v ' ' e ' '
        while(ctl.first_accept(::isalpha)) {
            auto name = variant_name();
            ctl.eat(' ');

            if(ctl.peek() == ')') {
                return variant_value(name);
            }

            local[name] = expression();
        }
        return expression();
    }

    Int variant_value(const string &name) {
        for(auto &scope : symbols) {
            if(scope.contains(name)) return scope[name];
        }
        return {}; // Unreachable.
    }

    string variant_name() {
        string name;
        while(ctl.accept(::isdigit, ::isalpha)) {
            name += ctl.pop();
        }
        return name;
    }
};

Link

LeetCode-736 Parse Lisp Expression