Skip to content

736. Parse Lisp Expression

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
 public:
  int evaluate(string expression) {
    return evaluate(expression, unordered_map<string, int>());
  }

 private:
  int evaluate(const string& e, unordered_map<string, int> scope) {
    if (isdigit(e[0]) || e[0] == '-')
      return stoi(e);
    if (const auto it = scope.find(e); it != scope.cend())
      return it->second;

    const int spaceIndex = e.find_first_of(' ');
    const string nextExpression =
        e.substr(spaceIndex + 1, e.length() - spaceIndex - 2);  // -2: "()"
    const vector<string> tokens = split(nextExpression);

    // Note that e[0] == '('.
    if (e[1] == 'm')  // 'mult'
      return evaluate(tokens[0], scope) * evaluate(tokens[1], scope);
    if (e[1] == 'a')  // 'add'
      return evaluate(tokens[0], scope) + evaluate(tokens[1], scope);

    // 'let'
    for (int i = 0; i + 1 < tokens.size(); i += 2)
      scope[tokens[i]] = evaluate(tokens[i + 1], scope);
    return evaluate(tokens.back(), scope);
  };

  vector<string> split(const string& e) {
    vector<string> tokens;
    string s;
    int opened = 0;

    for (const char c : e) {
      if (c == '(')
        ++opened;
      else if (c == ')')
        --opened;
      if (opened == 0 && c == ' ') {
        tokens.push_back(s);
        s = "";
      } else {
        s += c;
      }
    }

    if (!s.empty())
      tokens.push_back(s);
    return tokens;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
  public int evaluate(String expression) {
    return evaluate(expression, new HashMap<>());
  }

  private int evaluate(final String e, Map<String, Integer> prevScope) {
    if (Character.isDigit(e.charAt(0)) || e.charAt(0) == '-')
      return Integer.parseInt(e);
    if (prevScope.containsKey(e))
      return prevScope.get(e);

    Map<String, Integer> scope = new HashMap<>();
    scope.putAll(prevScope);

    final int spaceIndex = e.indexOf(' ');
    // +1 and -1 because of "()".
    final String nextExpression = e.substring(spaceIndex + 1, e.length() - 1);
    List<String> tokens = split(nextExpression);

    if (e.startsWith("(m")) // 'mult'
      return evaluate(tokens.get(0), scope) * evaluate(tokens.get(1), scope);
    if (e.startsWith("(a")) // 'add'
      return evaluate(tokens.get(0), scope) + evaluate(tokens.get(1), scope);

    // 'let'
    for (int i = 0; i < tokens.size() - 2; i += 2)
      scope.put(tokens.get(i), evaluate(tokens.get(i + 1), scope));
    return evaluate(tokens.get(tokens.size() - 1), scope);
  }

  private List<String> split(final String s) {
    List<String> tokens = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    int opened = 0;

    for (char c : s.toCharArray()) {
      if (c == '(')
        ++opened;
      else if (c == ')')
        --opened;
      if (opened == 0 && c == ' ') {
        tokens.add(sb.toString());
        sb.setLength(0);
      } else {
        sb.append(c);
      }
    }

    if (sb.length() > 0)
      tokens.add(sb.toString());
    return tokens;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
  def evaluate(self, expression: str) -> int:
    def evaluate(e: str, prevScope: dict) -> int:
      if e[0].isdigit() or e[0] == '-':
        return int(e)
      if e in prevScope:
        return prevScope[e]

      scope = prevScope.copy()
      nextExpression = e[e.index(' ') + 1:-1]
      tokens = parse(nextExpression)

      if e[1] == 'm':  # 'mult'
        return evaluate(tokens[0], scope) * evaluate(tokens[1], scope)
      if e[1] == 'a':  # 'add'
        return evaluate(tokens[0], scope) + evaluate(tokens[1], scope)

      # 'let'
      for i in range(0, len(tokens) - 2, 2):
        scope[tokens[i]] = evaluate(tokens[i + 1], scope)

      return evaluate(tokens[-1], scope)

    def parse(e: str):
      tokens = []
      s = ''
      opened = 0

      for c in e:
        if c == '(':
          opened += 1
        elif c == ')':
          opened -= 1
        if opened == 0 and c == ' ':
          tokens.append(s)
          s = ''
        else:
          s += c

      if len(s) > 0:
        tokens.append(s)
      return tokens

    return evaluate(expression, {})