Parse Lisp Expression is a recursion-and-scope problem. It looks scary because the input is a string of nested parentheses, but underneath it is a clean recursive evaluator with one twist: a stack of variable scopes that you push when a let binds a variable and pop when that let finishes.
Problem. Evaluate a Lisp-like expression and return its integer value. An expression is one of:
an integer, a variable name, or a parenthesized form: (add e1 e2), (mult e1 e2), or
(let v1 e1 v2 e2 ... body). A let binds each name to its value, then evaluates body. A variable
resolves to its innermost binding.
Example: (let x 2 (add x (let x 3 (mult x 4)))) → 14. The inner let rebinds x to 3 only
while computing (mult x 4) = 12; outside it, x is still 2, so add 2 12 = 14.
The slow way first
You could try to flatten everything into one giant dictionary of variables. But that breaks immediately on shadowing: the inner let sets x = 3, and if you overwrite the single dictionary entry, the outer x = 2 is gone forever. When the inner let ends you have no way to get the old value back.
The question to ask: how do I undo a binding once I leave the block that created it? You need to remember the previous value so you can restore it.
The idea: a scope stack you push and pop
Keep scopes on a stack. Each let pushes a fresh frame holding the names it binds, evaluates its body under that stack, then pops the frame. To look up a variable, scan the stack from the top down and take the first match — that is automatically the innermost binding. Popping restores the outer scope for free.
The whole algorithm is one recursive function plus this stack. An integer evaluates to itself; a name is a lookup; add/mult recurse on two arguments; let is the push-evaluate-pop dance.
Walk through it
Step through the animation. The outer let pushes x = 2. Inside add, the first x looks up to 2. Then the inner let pushes x = 3, shadowing the outer binding, so (mult x 4) gives 3 * 4 = 12. The moment the inner let returns, its frame is popped and x is 2 again — watch the scope label shrink. Finally add 2 12 = 14, and the outer frame pops too.
Pseudocode
evaluate(expr, scope):
if expr is an integer: return that integer
if expr is a variable name: return its value from the top-down scope lookup
parse the operator and arguments
if operator is add or mult:
a = evaluate(arg1, scope)
b = evaluate(arg2, scope)
return a+b or a*b
# it is a let
push a new frame onto the scope stack
for each (name, value) pair: bind name -> evaluate(value, scope)
result = evaluate(body, scope)
pop the frame # restore the outer scope
return resultThe Python solution
def evaluate(expr, scope):
if expr[0] != '(':
return int(expr) if is_int(expr) else lookup(scope, expr)
op, args = parse(expr)
if op in ('add', 'mult'):
a = evaluate(args[0], scope)
b = evaluate(args[1], scope)
return a + b if op == 'add' else a * b
pairs, body = split_let(args)
for name, value in pairs:
scope.push(name, evaluate(value, scope))
result = evaluate(body, scope)
scope.pop()
return result- The base case (lines 2–3): a token with no parenthesis is either an integer or a variable name resolved by
lookup, which scans the scope stack from the top down for the innermost binding. - Lines 5–8 handle
addandmult: evaluate both arguments recursively, then combine. - Line 9 splits a
letbody into its(name, value)pairs and the trailing body expression. - Lines 10–11 push each binding. A value is itself evaluated under the scope built so far, so later pairs can use earlier ones.
- Line 12 evaluates the body, line 13 pops the frame to undo the bindings, and line 14 returns — the pop is what restores the outer scope.
Complexity
| Case | Time | Notes |
|---|---|---|
| Parse + evaluate | O(n) (moderate) | each token visited a constant number of times |
| Variable lookup | O(d) (moderate) | d = nesting depth of let blocks |
O(d) (moderate)Here n is the size of the expression and d is how deeply let blocks nest. The scope stack is at most d frames deep, which is also the recursion depth.
When this pattern shows up
Whenever a problem has nested blocks with their own local variables — interpreters, calculators, config with overrides, JSON-with-scopes — reach for a scope stack: push on entry, pop on exit, look up from the top down. The pop is what makes shadowing and restoration just work.
Do not forget to pop. If you push a frame on every let but never pop, an inner binding leaks into the
outer scope and later lookups return the wrong value. Also evaluate each let value under the scope
built so far, not the final scope, or sequential bindings that depend on earlier ones break.
Practice
In (let x 2 (add x (let x 3 (mult x 4)))), what does the outer x resolve to right after the inner let pops its frame?
1. Why use a stack of scopes instead of a single dictionary?
2. How does a variable lookup pick the right binding?
3. What is the value of (let x 3 (mult x 4)) on its own?
4. What happens if you push a let frame but never pop it?