1
class Solution:
2
    def evaluate(self, expression: str) -> int:
3
        loc = {}
4
        stack = []
5
        for i, x in enumerate(expression):
6
            if x == "(":
7
                stack.append(i)
8
            elif x == ")":
9
                loc[stack.pop()] = i
10

11
        def fn(lo, hi, mp):
12
            """Return value of given expression."""
13
            if expression[lo] == "(":
14
                return fn(lo + 1, hi - 1, mp)
15
            i = lo
16
            vals = []
17
            while i < hi:
18
                if expression[i : i + 3] in ("let", "add"):
19
                    op = expression[i : i + 3]
20
                    i += 3
21
                elif expression[i : i + 4] == "mult":
22
                    op = "mult"
23
                    i += 4
24
                elif expression[i].isalpha():
25
                    x = ""
26
                    while i < hi and expression[i].isalnum():
27
                        x += expression[i]
28
                        i += 1
29
                    if op in ("add", "mult"):
30
                        vals.append(mp[x])
31
                elif expression[i].isdigit() or expression[i] == "-":
32
                    v = ""
33
                    while i < hi and (expression[i].isdigit() or expression[i] == "-"):
34
                        v += expression[i]
35
                        i += 1
36
                    if op == "let":
37
                        mp[x] = int(v)
38
                    else:
39
                        vals.append(int(v))
40
                elif expression[i] == "(":
41
                    v = fn(i + 1, loc[i], mp.copy())
42
                    i = loc[i] + 1
43
                    if op == "let":
44
                        mp[x] = v
45
                    else:
46
                        vals.append(v)
47
                else:
48
                    i += 1
49
            if op == "let":
50
                return int(v)
51
            elif op == "add":
52
                return sum(vals)
53
            else:
54
                return reduce(mul, vals)
55

56
        return fn(0, len(expression), {})