736. Parse Lisp Expression

https://leetcode.com/problems/parse-lisp-expression/description/

写一个简易的lisp expr parser，要支持三种表达式: (add x y)表示x+y, (mul x y)表示x * y，(let var1 e1 var2 e2 ... last_expr)表示e1赋给var1, e2赋给var2...最后整个表达式的值为last_expr的值。虽然这里有很多括号，但和之前遇到过的eval basket之类的用stack evaluate常量表达式的题不一样，这里()并不表示优先级而是最为表达式的分隔符，且还引入了变量的概念。解法很直观，分治递归解每个子表达式，然后把每个返回值再拼起来解当前的表达式。为了支持变量，每个表达式当作一个函数看待，用deque模拟call stack存储每个表达式产生的变量。

代码参考了花花的。

/*
 * @lc app=leetcode id=736 lang=cpp
 *
 * [736] Parse Lisp Expression
 *
 * https://leetcode.com/problems/parse-lisp-expression/description/
 *
 * algorithms
 * Hard (45.07%)
 * Likes:    183
 * Dislikes: 152
 * Total Accepted:    7.9K
 * Total Submissions: 17.5K
 * Testcase Example:  '"(add 1 2)"'
 *
 * 
 * You are given a string expression representing a Lisp-like expression to
 * return the integer value of.
 * 
 * The syntax for these expressions is given as follows.
 * 
 * An expression is either an integer, a let-expression, an add-expression, a
 * mult-expression, or an assigned variable.  Expressions always evaluate to a
 * single integer.
 * 
 * (An integer could be positive or negative.)
 * 
 * A let-expression takes the form (let v1 e1 v2 e2 ... vn en expr), where let
 * is always the string "let", then there are 1 or more pairs of alternating
 * variables and expressions, meaning that the first variable v1 is assigned
 * the value of the expression e1, the second variable v2 is assigned the value
 * of the expression e2, and so on sequentially; and then the value of this
 * let-expression is the value of the expression expr.
 * 
 * An add-expression takes the form (add e1 e2) where add is always the string
 * "add", there are always two expressions e1, e2, and this expression
 * evaluates to the addition of the evaluation of e1 and the evaluation of e2.
 * 
 * A mult-expression takes the form (mult e1 e2) where mult is always the
 * string "mult", there are always two expressions e1, e2, and this expression
 * evaluates to the multiplication of the evaluation of e1 and the evaluation
 * of e2.
 * 
 * For the purposes of this question, we will use a smaller subset of variable
 * names.  A variable starts with a lowercase letter, then zero or more
 * lowercase letters or digits.  Additionally for your convenience, the names
 * "add", "let", or "mult" are protected and will never be used as variable
 * names.
 * 
 * Finally, there is the concept of scope.  When an expression of a variable
 * name is evaluated, within the context of that evaluation, the innermost
 * scope (in terms of parentheses) is checked first for the value of that
 * variable, and then outer scopes are checked sequentially.  It is guaranteed
 * that every expression is legal.  Please see the examples for more details on
 * scope.
 * 
 * 
 * Evaluation Examples:
 * 
 * Input: (add 1 2)
 * Output: 3
 * 
 * Input: (mult 3 (add 2 3))
 * Output: 15
 * 
 * Input: (let x 2 (mult x 5))
 * Output: 10
 * 
 * Input: (let x 2 (mult x (let x 3 y 4 (add x y))))
 * Output: 14
 * Explanation: In the expression (add x y), when checking for the value of the
 * variable x,
 * we check from the innermost scope to the outermost in the context of the
 * variable we are trying to evaluate.
 * Since x = 3 is found first, the value of x is 3.
 * 
 * Input: (let x 3 x 2 x)
 * Output: 2
 * Explanation: Assignment in let statements is processed sequentially.
 * 
 * Input: (let x 1 y 2 x (add x y) (add x y))
 * Output: 5
 * Explanation: The first (add x y) evaluates as 3, and is assigned to x.
 * The second (add x y) evaluates as 3+2 = 5.
 * 
 * Input: (let x 2 (add (let x 3 (let x 4 x)) x))
 * Output: 6
 * Explanation: Even though (let x 4 x) has a deeper scope, it is outside the
 * context
 * of the final x in the add-expression.  That final x will equal 2.
 * 
 * Input: (let a1 3 b2 (add a1 1) b2) 
 * Output 4
 * Explanation: Variable names can contain digits after the first character.
 * 
 * 
 * 
 * Note:
 * The given string expression is well formatted: There are no leading or
 * trailing spaces, there is only a single space separating different
 * components of the string, and no space between adjacent parentheses.  The
 * expression is guaranteed to be legal and evaluate to an integer.
 * The length of expression is at most 2000.  (It is also non-empty, as that
 * would not be a legal expression.)
 * The answer and all intermediate calculations of that answer are guaranteed
 * to fit in a 32-bit integer.
 * 
 */
class Solution {
public:
    deque<unordered_map<string, int>> scopes;
    int eval(const string &s, int &pos) {
        // 支持遍历的call stack
        scopes.push_front(unordered_map<string, int>());
        int val = 0;
        if (s[pos] == '(') ++pos;
        const string t = token(s, pos);
        if (t == "add") {
            val = eval(s, ++pos) + eval(s, ++pos);
        } else if (t == "mult") {
            val = eval(s, ++pos) * eval(s, ++pos);
        } else if (t == "let") {
            string var;
            // expecting " var1 exp1 var2 exp2 ... last_expr"
            while (s[pos] != ')') {
                ++pos;
                // 每个eval会消耗它自身的()，当pos在这里还遇到(说明它是last_expr
                if (s[pos] == '(') {
                    val = eval(s, ++pos);
                    break;
                }
                // x (add x y) 的x 或 -12)的-12
                var = token(s, pos);
                // 是 -12)
                if (s[pos] == ')') {
                    if (isalpha(var[0])) val = value(var);
                    else val = stoi(var);
                    break;
                }
                // (add x y)
                val = scopes.front()[var] = eval(s, ++pos);
            }
        } else if (isalpha(t[0])) {
            // var
            val = value(t);
        } else {
            val = stoi(t);
        }
        if (s[pos] == ')') ++pos;
        scopes.pop_front();
        return val;
    }

    int value(const string &symbol) {
        // 遍历call stack直到找到var的值
        for (const auto &scope : scopes) {
            if (scope.count(symbol)) return scope.at(symbol);
        }
        return 0;
    }

    string token(const string &s, int &pos) {
        string token;
        while (pos < s.length()) {
            if (s[pos] == ')' || s[pos] == ' ') break;
            token += s[pos++];
        }
        return token;
    }

    int evaluate(string expression) {
        int pos = 0;
        return eval(expression, pos);
    }
};