736. Parse Lisp Expression

• Difficulty: Hard

• Topics: String

• Similar Questions:

  • Ternary Expression Parser

  • Number of Atoms

  • Basic Calculator IV

Problem:

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.

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:

Solutions:

class Solution {
public:
    int evaluate(string expression) {
        int pos = 0;
        unordered_map<string, int> symbols;
        return helper(expression, pos, symbols);
    }
private:
    int getNumber(string& expression, int& pos) {
        int sign = 1;
        if (expression[pos] == '-') {
            sign = -1;
            ++pos;
        }

        int val = 0;
        for (; pos < expression.length() && isdigit(expression[pos]); ++pos) {
            val = 10 * val + (expression[pos] - '0');
        }

        return sign * val;
    }

    string getOperator(string& expression, int& pos) {
        string ret;
        for (; pos < expression.length() && expression[pos] != ' '; ++pos) {
            ret.push_back(expression[pos]);
        }

        return ret;
    }

    string getSymbol(string& expression, int& pos) {
        string ret;
        for (; pos < expression.length() && expression[pos] != ' ' && expression[pos] != ')'; ++pos) {
            ret.push_back(expression[pos]);
        }

        return ret;
    }

    int helper(string& expression, int& pos, unordered_map<string, int>& symbols) {
        if (expression[pos] == '(') {
            ++pos; // remove '('
            string op = getOperator(expression, pos);
            ++pos; // remove space
            if (op != "let") {
                int oprand1 = helper(expression, pos, symbols);
                ++pos; //remove space
                int oprand2 = helper(expression, pos, symbols);
                ++pos; // remove ')'
                if (op == "add") {
                    return oprand1 + oprand2;
                } else {
                    return oprand1 * oprand2;
                }
            } else {
                unordered_set<string> add;
                unordered_map<string, int> replace;

                string symbol1 = getSymbol(expression, pos);
                ++pos; // remove space;
                if (symbols.count(symbol1) > 0) {
                    replace[symbol1] = symbols[symbol1];
                } else {
                    add.insert(symbol1);
                }
                int value1 = helper(expression, pos, symbols);

                ++pos; // remove space;
                symbols[symbol1] = value1;

                while(true) {
                    int cur = pos;
                    int val = helper(expression, pos, symbols);

                    if (expression[pos] == ')') {
                        for (auto& symbol : add) {
                            symbols.erase(symbol);
                        }
                        for (auto& entry : replace) {
                            symbols[entry.first] = entry.second;
                        }
                        ++pos; // remove ')'
                        return val;
                    } else {
                        pos = cur;
                        string symbol = getSymbol(expression, pos);
                        ++pos; // remove space;
                        if (symbols.count(symbol) > 0 && add.count(symbol) == 0) {
                            replace[symbol] = symbols[symbol];
                        }

                        add.insert(symbol);

                        int value = helper(expression, pos, symbols);

                        ++pos; // remove space;
                        symbols[symbol] = value;
                    }
                }
            }
        } else if (expression[pos] == '-' || isdigit(expression[pos])){
            return getNumber(expression, pos);
        } else {
            string symbol = getSymbol(expression, pos);

            if (symbols.count(symbol) == 0) return -1;
            return symbols[symbol];
        }
    }

};