1
class Context {
2
  unordered_map<string_view, int> _map;
3
  const Context *_parent{};
4

5
 public:
6
  Context(const Context *parent) : _parent{parent} {
7
    ;
8
  }
9
  const Context *Parent() const {
10
    return _parent;
11
  }
12
  int GetValue(const string_view &key) const {
13
    auto it = _map.find(key);
14
    if (it != _map.end()) return it->second;
15
    if (_parent) return _parent->GetValue(key);
16
    assert(0);
17
    return numeric_limits<int>::min();
18
  }
19
  void AddValue(const string_view &key, int val) {
20
    auto [it, isInserted] = _map.emplace(key, val);
21
    if (!isInserted) it->second = val;
22
  }
23
};
24
class Solution {
25
  string_view symbol(string_view &expr) {
26
    string_view ret;
27
    if (expr.empty() || !isalpha(expr[0])) {
28
      return ret;
29
    }
30
    auto pos = expr.find_first_of(" )");
31
    assert(pos != string_view::npos);
32
    ret = expr.substr(0, pos);
33
    expr.remove_prefix(pos);
34
    return ret;
35
  }
36
  int evaluate(string_view &expr, Context *context) {
37
    assert(!expr.empty());
38
    if (expr[0] == '(') {
39
      assert(expr.length() >= 4);
40
      if (expr.substr(0, 4) == "(add") {
41
        assert(expr.length() > 4);
42
        expr.remove_prefix(4);
43
        assert(!expr.empty() && expr[0] == ' ');
44
        expr.remove_prefix(1);
45
        int l = evaluate(expr, context);
46
        assert(!expr.empty() && expr[0] == ' ');
47
        expr.remove_prefix(1);
48
        int r = evaluate(expr, context);
49
        assert(!expr.empty() && expr[0] == ')');
50
        expr.remove_prefix(1);
51
        return l + r;
52
      }
53
      if (expr.substr(0, 4) == "(mul") {
54
        assert(expr.length() > 5);
55
        expr.remove_prefix(5);
56
        assert(!expr.empty() && expr[0] == ' ');
57
        expr.remove_prefix(1);
58
        int l = evaluate(expr, context);
59
        assert(!expr.empty() && expr[0] == ' ');
60
        expr.remove_prefix(1);
61
        int r = evaluate(expr, context);
62
        assert(!expr.empty() && expr[0] == ')');
63
        expr.remove_prefix(1);
64
        return l * r;
65
      }
66
      if (expr.substr(0, 4) == "(let") {
67
        assert(expr.length() > 4);
68
        expr.remove_prefix(4);
69
        Context nc(context);
70
        while (1) {
71
          assert(!expr.empty() && expr[0] == ' ');
72
          expr.remove_prefix(1);
73
          string_view sym = symbol(expr);
74
          assert(!expr.empty());
75
          if (sym.empty() || expr[0] == ')') {
76
            int ret{};
77
            if (sym.empty()) {
78
              ret = evaluate(expr, &nc);
79
            } else {
80
              ret = nc.GetValue(sym);
81
            }
82
            assert(!expr.empty() && expr[0] == ')');
83
            expr.remove_prefix(1);
84
            return ret;
85
          }
86
          assert(!expr.empty() && expr[0] == ' ');
87
          expr.remove_prefix(1);
88
          int value = evaluate(expr, &nc);
89
          nc.AddValue(sym, value);
90
        }
91
        assert(0);
92
      }
93
    }
94
    if (isdigit(expr[0]) || expr[0] == '-') {
95
      auto pos = expr.find_first_not_of("-0123456789");
96
      auto len = min(expr.length(), pos);
97
      int num;
98
      if (auto [ptr, ec] = from_chars(expr.data(), expr.data() + len, num); ec == errc()) {
99
        expr.remove_prefix(len);
100
      } else {
101
        assert(0);
102
      }
103
      return num;
104
    }
105
    if (isalpha(expr[0])) {
106
      string_view sym = symbol(expr);
107
      assert(!expr.empty() && (expr[0] == ' ' || expr[0] == ')'));
108
      return context->GetValue(sym);
109
    }
110
    assert(0);
111
    return numeric_limits<int>::min();
112
  }
113

114
 public:
115
  int evaluate(string expression) {
116
    string_view expr(expression);
117
    Context context(nullptr);
118
    return evaluate(expr, &context);
119
  }
120
};