LeetCode 736 - Parse Lisp Expression

The problem asks us to evaluate a Lisp-like expression represented as a string. The expression can contain integers, variables, and three special operations: let, add, and mult. An expression evaluates to a single integer value.

leetcodehardhash-tablestringstackrecursion

LeetCode Problem 736

Difficulty: 🔴 Hard
Topics: Hash Table, String, Stack, Recursion

Solution

Problem Understanding

The problem asks us to evaluate a Lisp-like expression represented as a string. The expression can contain integers, variables, and three special operations: let, add, and mult.

An expression evaluates to a single integer value. The challenge is not arithmetic itself, but correctly handling nested scopes and variable shadowing.

A let expression introduces variable assignments. These assignments are processed sequentially, and each assignment becomes visible to later expressions inside the same let. Variables can also shadow outer variables. This means a variable defined in an inner scope temporarily overrides a variable with the same name from an outer scope.

For example:

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

Inside the inner let, x becomes 3, even though an outer x = 2 already exists. Therefore:

(add x y) = 3 + 4 = 7
(mult x 7) = 2 * 7 = 14

The input is always a valid expression, and every variable reference is guaranteed to resolve correctly. This guarantee simplifies error handling because we never need to deal with malformed syntax or undefined variables.

The constraints are relatively small:

  • Expression length is at most 2000
  • Nested expressions are possible
  • Variable scopes can overlap deeply

A naive parser that repeatedly copies environments or reparses substrings can become inefficient. We therefore want a solution that parses the string incrementally and maintains scope efficiently.

Several edge cases are important:

  • Nested scopes where variables shadow outer values
  • Sequential assignments inside let
  • Negative integers
  • Expressions consisting of only a single integer
  • Expressions consisting of only a variable lookup
  • Deeply nested recursive expressions

The input is guaranteed to be syntactically correct, which means we can focus entirely on evaluation logic.

Approaches

Brute Force Approach

A brute force solution would repeatedly parse substrings and construct entirely new variable environments for every nested expression.

For each let expression, we could:

  1. Copy the current scope map
  2. Apply assignments
  3. Recursively evaluate the final expression

Similarly, every recursive call might create new substrings for tokens and nested expressions.

This approach works because each recursive evaluation sees a correct snapshot of the variable environment. However, copying entire hash maps at every nested scope becomes expensive, especially when expressions are deeply nested.

Repeated substring creation also increases overhead because string slicing and reparsing may revisit the same characters multiple times.

Optimal Approach

The key insight is that Lisp expressions naturally form a recursive structure, and scope behaves like a stack.

Instead of copying entire environments, we maintain:

  • A parsing pointer into the string
  • A hash map from variable name to a stack of values

When entering a new scope, we push new variable values onto stacks. When leaving the scope, we pop them off. This exactly matches lexical scoping behavior.

For example:

x = 2
(let x 3 ...)

The stack for x becomes:

[2, 3]

When the inner scope ends, we pop 3 and restore 2.

This allows efficient scope management without copying large maps repeatedly.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n²) Repeated environment copying and substring parsing
Optimal O(n) O(n) Single-pass recursive parser with scoped stacks

Algorithm Walkthrough

  1. Maintain a global parsing index into the expression string.

Instead of creating substrings repeatedly, we move a pointer through the original string. Every recursive call continues parsing from the current position. 2. Use a hash map where each variable maps to a stack of values.

This structure models nested scope naturally. The most recent assignment is always the active value. 3. Define a recursive parse() function.

This function evaluates the expression starting at the current index and returns its integer value. 4. If the current character is not '(', parse either:

  • An integer
  • A variable name

If it is a variable, return the top value from its stack. 5. If the current character is '(', parse an operation.

Skip '(', then read the operation name:

  • add
  • mult
  • let
  1. For add:
  • Parse first expression
  • Parse second expression
  • Return their sum
  1. For mult:
  • Parse first expression
  • Parse second expression
  • Return their product
  1. For let:

Process tokens sequentially.

Each iteration can be either:

  • A variable assignment pair
  • The final expression
  1. For every variable assignment:
  • Parse variable name
  • Parse assigned expression
  • Push value onto that variable's stack
  • Record the variable so we can pop it later
  1. Once the final expression is reached:
  • Evaluate it
  • Pop all variables introduced in this scope
  • Return the result
  1. Continue recursively until the entire expression is evaluated.

Why it works

The correctness comes from maintaining a stack of values for each variable. The top of the stack always represents the innermost visible scope. Entering a scope pushes values, and leaving a scope pops them. Since recursive parsing follows the exact nesting structure of the expression, variable visibility always matches Lisp scoping rules.

Python Solution

from collections import defaultdict
from typing import DefaultDict, List

class Solution:
    def evaluate(self, expression: str) -> int:
        index = 0
        scope: DefaultDict[str, List[int]] = defaultdict(list)

        def parse() -> int:
            nonlocal index

            # Integer or variable
            if expression[index] != '(':
                if expression[index] == '-' or expression[index].isdigit():
                    start = index

                    if expression[index] == '-':
                        index += 1

                    while index < len(expression) and expression[index].isdigit():
                        index += 1

                    return int(expression[start:index])

                start = index

                while (
                    index < len(expression)
                    and expression[index] not in [' ', ')']
                ):
                    index += 1

                variable = expression[start:index]
                return scope[variable][-1]

            # Skip '('
            index += 1

            start = index

            while expression[index] != ' ':
                index += 1

            operation = expression[start:index]
            index += 1

            if operation == "add":
                first = parse()
                index += 1
                second = parse()
                index += 1
                return first + second

            if operation == "mult":
                first = parse()
                index += 1
                second = parse()
                index += 1
                return first * second

            # let expression
            assigned_variables = []

            while True:
                if expression[index] == '(':
                    result = parse()
                    break

                start = index

                while (
                    index < len(expression)
                    and expression[index] not in [' ', ')']
                ):
                    index += 1

                token = expression[start:index]

                # Final expression
                if expression[index] == ')':
                    result = scope[token][-1]
                    break

                index += 1

                # Detect final expression instead of assignment
                if (
                    expression[index] == '('
                    or expression[index] == '-'
                    or expression[index].isdigit()
                ):
                    result = parse()
                    break

                value = parse()
                scope[token].append(value)
                assigned_variables.append(token)

                if expression[index] == ' ':
                    index += 1

            for variable in assigned_variables:
                scope[variable].pop()

            index += 1
            return result

        return parse()

The implementation revolves around recursive descent parsing.

The index variable tracks the current parsing position globally. This avoids repeatedly creating substrings and enables a true single-pass parser.

The scope hash map stores stacks of values for variables. Each variable may have multiple active bindings due to nested scopes.

The parse() function evaluates one expression at the current index.

If the expression does not begin with '(', it must be either:

  • An integer
  • A variable reference

Integers are parsed directly. Variables are resolved by reading the top value from their stack.

For compound expressions, the parser first reads the operation name.

The add and mult operations are straightforward because they always contain exactly two expressions.

The let operation is more complicated because it mixes assignments and a final expression. The parser processes tokens sequentially until it detects the final expression.

Every assigned variable is recorded so its scope can later be removed correctly when exiting the let.

This implementation matches Lisp scoping rules exactly.

Go Solution

package main

import (
	"strconv"
)

func evaluate(expression string) int {
	index := 0
	scope := map[string][]int{}

	var parse func() int

	parse = func() int {
		// Integer or variable
		if expression[index] != '(' {
			// Integer
			if expression[index] == '-' || (expression[index] >= '0' && expression[index] <= '9') {
				start := index

				if expression[index] == '-' {
					index++
				}

				for index < len(expression) &&
					expression[index] >= '0' &&
					expression[index] <= '9' {
					index++
				}

				value, _ := strconv.Atoi(expression[start:index])
				return value
			}

			// Variable
			start := index

			for index < len(expression) &&
				expression[index] != ' ' &&
				expression[index] != ')' {
				index++
			}

			variable := expression[start:index]
			values := scope[variable]
			return values[len(values)-1]
		}

		// Skip '('
		index++

		start := index

		for expression[index] != ' ' {
			index++
		}

		operation := expression[start:index]
		index++

		if operation == "add" {
			first := parse()
			index++
			second := parse()
			index++

			return first + second
		}

		if operation == "mult" {
			first := parse()
			index++
			second := parse()
			index++

			return first * second
		}

		// let expression
		assigned := []string{}
		var result int

		for {
			if expression[index] == '(' {
				result = parse()
				break
			}

			start := index

			for index < len(expression) &&
				expression[index] != ' ' &&
				expression[index] != ')' {
				index++
			}

			token := expression[start:index]

			// Final variable expression
			if expression[index] == ')' {
				values := scope[token]
				result = values[len(values)-1]
				break
			}

			index++

			// Final expression
			if expression[index] == '(' ||
				expression[index] == '-' ||
				(expression[index] >= '0' && expression[index] <= '9') {
				result = parse()
				break
			}

			value := parse()

			scope[token] = append(scope[token], value)
			assigned = append(assigned, token)

			if expression[index] == ' ' {
				index++
			}
		}

		for _, variable := range assigned {
			values := scope[variable]
			scope[variable] = values[:len(values)-1]
		}

		index++
		return result
	}

	return parse()
}

The Go implementation closely mirrors the Python version, but several language-specific details differ.

Go does not have Python's defaultdict, so the scope map is initialized manually using map[string][]int.

Slice operations naturally support stack behavior. Appending pushes values, and slicing removes the top value.

Integer parsing uses strconv.Atoi.

Unlike Python, Go requires explicit character comparisons for digit checks.

Go integers are safe here because the problem guarantees all intermediate values fit within 32-bit signed integer range.

Worked Examples

Example 1

(let x 2 (mult x (let x 3 y 4 (add x y))))
Step Current Expression Scope State Result
1 let x 2 ... x = [2]
2 mult x ... x = [2]
3 evaluate x x = [2] 2
4 inner let x 3 x = [2, 3]
5 y 4 x = [2, 3], y = [4]
6 add x y x = [2, 3], y = [4] 7
7 mult 2 7 x = [2] 14

Final result:

14

Example 2

(let x 3 x 2 x)
Step Action Scope
1 assign x = 3 x = [3]
2 assign x = 2 x = [3, 2]
3 evaluate x x = [3, 2]

The visible value is the top of the stack:

2

Example 3

(let x 1 y 2 x (add x y) (add x y))
Step Action Scope
1 x = 1 x = [1]
2 y = 2 x = [1], y = [2]
3 x = add(x, y) = 3 x = [1, 3], y = [2]
4 evaluate add(x, y) x = [1, 3], y = [2]

Final computation:

3 + 2 = 5

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is parsed at most once
Space O(n) Recursive calls and scope stacks may store all variables

The parser advances through the string exactly once. Every token and character participates in constant work, making the overall runtime linear.

Space usage comes from two sources:

  • Recursive call stack for nested expressions
  • Variable stacks for active scopes

In the worst case, deeply nested expressions may require linear auxiliary memory.

Test Cases

sol = Solution()

assert sol.evaluate("1") == 1  # single integer
assert sol.evaluate("-5") == -5  # negative integer

assert sol.evaluate("(add 1 2)") == 3  # basic addition
assert sol.evaluate("(mult 3 4)") == 12  # basic multiplication

assert sol.evaluate("(let x 2 x)") == 2  # simple variable assignment

assert sol.evaluate(
    "(let x 2 (mult x (let x 3 y 4 (add x y))))"
) == 14  # nested scope shadowing

assert sol.evaluate(
    "(let x 3 x 2 x)"
) == 2  # sequential reassignment

assert sol.evaluate(
    "(let x 1 y 2 x (add x y) (add x y))"
) == 5  # assignment using previous expressions

assert sol.evaluate(
    "(let x 2 y (add x 3) (mult y 2))"
) == 10  # variable depending on previous variable

assert sol.evaluate(
    "(let a1 3 b2 (mult a1 2) (add b2 a1))"
) == 9  # variables containing digits

assert sol.evaluate(
    "(mult (add 2 3) (add 4 5))"
) == 45  # nested arithmetic expressions

assert sol.evaluate(
    "(let x 1 (let x 2 (let x 3 x)))"
) == 3  # deeply nested shadowing

assert sol.evaluate(
    "(let x 5 (add x (mult x 2)))"
) == 15  # variable reuse

assert sol.evaluate(
    "(let x -2 y 3 (add x y))"
) == 1  # negative values inside expressions
Test Why
"1" Validates direct integer parsing
"-5" Validates negative integer handling
"(add 1 2)" Tests addition
"(mult 3 4)" Tests multiplication
"(let x 2 x)" Tests simple variable lookup
Nested shadowing example Tests lexical scoping
Sequential reassignment Tests let evaluation order
Assignment from expression Tests dependent assignments
Variables with digits Tests variable parsing rules
Nested arithmetic Tests recursive parsing
Deep shadow nesting Tests multiple scope levels
Variable reuse Tests repeated variable access
Negative values Tests arithmetic with negatives

Edge Cases

One important edge case is variable shadowing across nested scopes. Expressions like:

(let x 1 (let x 2 x))

can easily produce incorrect results if scope restoration is not handled properly. A naive implementation might overwrite the outer value permanently. Using a stack for each variable solves this cleanly because inner values are pushed and later popped automatically.

Another tricky case is sequential assignment inside a single let expression. In:

(let x 1 y (add x 2) y)

the assignment to y must see the already assigned value of x. Processing assignments sequentially is therefore essential. The implementation evaluates and stores each assignment immediately before moving to the next token.

Negative integers are also easy to mishandle. Since variable names contain lowercase letters and digits, a leading - unambiguously indicates an integer. The parser explicitly checks for '-' before digit parsing, ensuring negative values are interpreted correctly.

A final subtle edge case is distinguishing between the final expression of a let and another assignment pair. The implementation determines this by examining what follows the token. If the next component represents an expression instead of a variable assignment, parsing switches to evaluating the final expression directly.