Parse Lisp Expression

hard stack recursion string parsing

Problem

Given a string expression of the Lisp variants (let v1 e1 v2 e2 ... expr), (add a b) and (mult a b), evaluate it and return the integer result. Variables follow lexical scoping.

Input"(let x 2 (mult x (let x 3 y 4 (add x y))))"

Output14

Inner let temporarily binds x=3, evaluates add x y = 7, then mult 2 * 7 = 14.

input

def evaluate(expression):
    def parse(tokens, scope):
        if tokens[0] != '(':
            t = tokens.pop(0)
            return int(t) if t.lstrip('-').isdigit() else scope[t]
        tokens.pop(0)
        op = tokens.pop(0)
        if op == 'add' or op == 'mult':
            a, b = parse(tokens, scope), parse(tokens, scope)
            tokens.pop(0)
            return a + b if op == 'add' else a * b
        new_scope = dict(scope)
        while True:
            if tokens[0] == '(' or (tokens[1] == ')' if len(tokens) > 1 else True):
                val = parse(tokens, new_scope); tokens.pop(0); return val
            name = tokens.pop(0)
            new_scope[name] = parse(tokens, new_scope)
    tokens = expression.replace('(', ' ( ').replace(')', ' ) ').split()
    return parse(tokens, {})

function evaluate(expression) {
  let i = 0;
  const tokens = [];
  let buf = '';
  for (const ch of expression) {
    if (ch === '(' || ch === ')' || ch === ' ') { if (buf) { tokens.push(buf); buf = ''; } if (ch !== ' ') tokens.push(ch); }
    else buf += ch;
  }
  if (buf) tokens.push(buf);
  function parse(scope) {
    if (tokens[i] !== '(') { const t = tokens[i++]; return /^-?\d+$/.test(t) ? +t : scope.get(t); }
    i++; const op = tokens[i++];
    if (op === 'add' || op === 'mult') { const a = parse(scope), b = parse(scope); i++; return op === 'add' ? a + b : a * b; }
    const s = new Map(scope);
    while (true) {
      if (tokens[i] === '(' || tokens[i+1] === ')') { const v = parse(s); i++; return v; }
      const name = tokens[i++]; s.set(name, parse(s));
    }
  }
  return parse(new Map());
}

class Solution {
  int i = 0; String[] tokens;
  public int evaluate(String expression) {
    tokens = expression.replace("(", " ( ").replace(")", " ) ").trim().split("\\s+");
    return parse(new HashMap<>());
  }
  int parse(Map<String,Integer> scope) {
    if (!tokens[i].equals("(")) { String t = tokens[i++]; return Character.isDigit(t.charAt(0)) || t.charAt(0) == '-' ? Integer.parseInt(t) : scope.get(t); }
    i++; String op = tokens[i++];
    if (op.equals("add") || op.equals("mult")) { int a = parse(scope), b = parse(scope); i++; return op.equals("add") ? a + b : a * b; }
    Map<String,Integer> s = new HashMap<>(scope);
    while (true) {
      if (tokens[i].equals("(") || tokens[i+1].equals(")")) { int v = parse(s); i++; return v; }
      String name = tokens[i++]; s.put(name, parse(s));
    }
  }
}

class Solution {
  int i = 0; vector<string> tokens;
public:
  int evaluate(string expression) {
    string buf;
    for (char ch : expression) {
      if (ch == '(' || ch == ')' || ch == ' ') { if (!buf.empty()) { tokens.push_back(buf); buf.clear(); } if (ch != ' ') tokens.push_back(string(1, ch)); }
      else buf.push_back(ch);
    }
    unordered_map<string,int> scope;
    return parse(scope);
  }
  int parse(unordered_map<string,int> scope) {
    if (tokens[i] != "(") { string t = tokens[i++]; return (isdigit(t[0]) || t[0]=='-') ? stoi(t) : scope[t]; }
    i++; string op = tokens[i++];
    if (op == "add" || op == "mult") { int a = parse(scope), b = parse(scope); i++; return op == "add" ? a + b : a * b; }
    while (true) {
      if (tokens[i] == "(" || tokens[i+1] == ")") { int v = parse(scope); i++; return v; }
      string name = tokens[i++]; scope[name] = parse(scope);
    }
  }
};

Explanation

This mini-Lisp nests expressions inside parentheses, so the cleanest approach is recursion where each call evaluates one expression and each let carries its own copy of the variable scope.

We first split the string into tokens (numbers, variable names, operators, and parentheses). The parse function looks at the next token: if it is not (, it is an atom — either an integer or a variable we look up in the current scope.

If it is (, we read the operator. For add or mult we recursively parse two operands and combine them. For let we make a fresh scope copied from the parent, then read name value pairs (the value itself is parsed recursively), binding each into the new scope, until the final body expression is reached and evaluated.

Example: "(let x 2 (mult x (let x 3 y 4 (add x y))))". The outer let binds x = 2. Inside, a new let temporarily rebinds x = 3 and y = 4, so add x y = 7; that result multiplies by the outer x = 2 to give 14.

It works because copying the scope for each let gives correct lexical scoping — inner bindings shadow outer ones but vanish when the inner expression finishes, exactly like nested blocks.

Time: O(n) Space: O(n)