1
class Solution {
2

3
  String expression;
4
  int index;
5
  HashMap<String, Deque<Integer>> scope;
6

7
  // variable may be assigned many times, we use the peek value
8

9
  public int evaluate(String expression) {
10
    this.expression = expression;
11
    index = 0;
12
    scope = new HashMap<>();
13
    return evaluate();
14
  }
15

16
  private int evaluate() {
17

18
    if (expression.charAt(index) == '(') {
19
      // this is an expression
20
      index++; // skip '('
21
      char begin = expression.charAt(index);
22
      int ret;
23
      if (begin == 'l') {
24
        // let
25
        index += 4; // skip let and a blank space
26
        ArrayList<String> vars = new ArrayList<>();
27
        while (true) {
28
          if (!Character.isLowerCase(expression.charAt(index))) {
29
            ret = evaluate();
30
            break;
31
          }
32
          String var = parseVar();
33
          if (expression.charAt(index) == ')') {
34
            ret = scope.get(var).peek();
35
            break;
36
          }
37
          vars.add(var);
38
          index++;
39
          int e = evaluate();
40
          scope.putIfAbsent(var, new LinkedList<>());
41
          scope.get(var).push(e); // assign a new value
42
          index++;
43
        }
44
        for (String var : vars) {
45
          scope.get(var).pop(); // remove all values of this scope
46
        }
47

48
      } else if (begin == 'a') {
49
        // add
50
        index += 4;
51
        int v1 = evaluate();
52
        index++;
53
        int v2 = evaluate();
54
        ret = v1 + v2;
55
      } else {
56
        // multi
57
        index += 5;
58
        int v1 = evaluate();
59
        index++;
60
        int v2 = evaluate();
61
        ret = v1 * v2;
62
      }
63
      index++; // skip ')'
64
      return ret;
65
    } else {
66
      // this is not a expression, this is an integer or a variable
67
      if (Character.isLowerCase(expression.charAt(index))) {
68
        // this is a variable, the current value is peek value
69
        String var = parseVar();
70
        return scope.get(var).peek();
71
      } else {
72
        // this is an integer
73
        return parseInt();
74
      }
75
    }
76
  }
77

78
  // read an integer
79
  private int parseInt() {
80
    boolean negative = false;
81
    if (expression.charAt(index) == '-') {
82
      negative = true;
83
      index++;
84
    }
85
    int ret = 0;
86
    while (Character.isDigit(expression.charAt(index))) {
87
      ret *= 10;
88
      ret += expression.charAt(index) - '0';
89
      index++;
90
    }
91
    if (negative) return -ret;
92
    return ret;
93
  }
94

95
  // read a variable
96
  private String parseVar() {
97
    StringBuilder sb = new StringBuilder();
98
    char c = expression.charAt(index);
99
    while (c != ' ' && c != ')') {
100
      sb.append(c);
101
      c = expression.charAt(++index);
102
    }
103
    return sb.toString();
104
  }
105
}