#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using std::deque;
using std::map;
using std::string;
using std::vector;

using std::cout; using std::endl;

class Solution {
public:
    int evaluate(string expression) {
        int pos = 0;
        return eval(expression, pos);
    }

private:
    int eval(string exp, int& pos) {
        int val = 0;
        scopes.push_front(map<string, int>());
        if (exp[pos] == '(') pos++;
        string token = get_token(exp, pos);
        if (token == "add") {
            int val1 = eval(exp, ++pos);
            int val2 = eval(exp, ++pos);
            val = val1 + val2;
        } else if (token == "mult") {
            int val1 = eval(exp, ++pos);
            int val2 = eval(exp, ++pos);
            val = val1 * val2;
        } else if (token == "let") {
            vector<string> exps;
            while (pos < exp.size() && exp[pos] == ' ')
                exps.push_back(get_expression(exp, ++pos));
            int j = 0;
            for (int i = 0; i < exps.size() - 1; i += 2, j = 0) {
                string var = exps[i];
                int v = eval(exps[i + 1], j);
                scopes.front()[var] = v;
            }
            val = eval(exps.back(), j);
        } else if (isalpha(token[0])) {
            val = find_value(token);
        } else {
            val = atoi(token.c_str());
        }
        if (pos < exp.size() && exp[pos] == ')') pos++;
        scopes.pop_front();
        return val;
    }

    string get_token(string exp, int& pos) {
        int beg = pos;
        while (exp[pos] != ' ' && exp[pos] != ')') pos++;
        return exp.substr(beg, pos - beg);
    }

    string get_expression(string exp, int& pos) {
        int beg = pos, cnt = 0;
        while (pos < exp.size() && (cnt != 0 || (exp[pos] != ' ' && exp[pos] != ')'))) {
            char c = exp[pos++];
            if (c == '(') cnt++;
            if (c == ')') cnt--;
        }
        return exp.substr(beg, pos - beg);
    }

    int find_value(string token) {
        for (auto it = scopes.cbegin(); it != scopes.cend(); ++it)
            if (it->count(token))
                return it->at(token);
        return 0;
    }

    deque<map<string, int>> scopes;
};

// (add 1 (let x 2 x))

int main() {
    Solution* sol = new Solution();

    cout << sol->evaluate("mult (add (add 1 3) 4) 5") << endl;
    cout << sol->evaluate("let x 3 y 9 x 1 x 4 (add x (let x 2 (add (add 1 x) 4)))") << endl;
    cout << sol->evaluate("(let x 1 y 2 x (add x y) (add x y))") << endl;

    return 0;
}