LeetCode #736 — HARD

Parse Lisp Expression

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode

The Problem

Problem Statement

You are given a string expression representing a Lisp-like expression to return the integer value of.

The syntax for these expressions is given as follows.

An expression is either an integer, let expression, add expression, mult expression, or an assigned variable. Expressions always evaluate to a single integer.
(An integer could be positive or negative.)
A let expression takes the form "(let v₁ e₁ v₂ e₂ ... v_n e_n expr)", where let is always the string "let", then there are one or more pairs of alternating variables and expressions, meaning that the first variable v₁ is assigned the value of the expression e₁, the second variable v₂ is assigned the value of the expression e₂, and so on sequentially; and then the value of this let expression is the value of the expression expr.
An add expression takes the form "(add e₁ e₂)" where add is always the string "add", there are always two expressions e₁, e₂ and the result is the addition of the evaluation of e₁ and the evaluation of e₂.
A mult expression takes the form "(mult e₁ e₂)" where mult is always the string "mult", there are always two expressions e₁, e₂ and the result is the multiplication of the evaluation of e1 and the evaluation of e2.
For this question, we will use a smaller subset of variable names. A variable starts with a lowercase letter, then zero or more lowercase letters or digits. Additionally, for your convenience, the names "add", "let", and "mult" are protected and will never be used as variable names.
Finally, there is the concept of scope. When an expression of a variable name is evaluated, within the context of that evaluation, the innermost scope (in terms of parentheses) is checked first for the value of that variable, and then outer scopes are checked sequentially. It is guaranteed that every expression is legal. Please see the examples for more details on the scope.

Example 1:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14
Explanation: In the expression (add x y), when checking for the value of the variable x,
we check from the innermost scope to the outermost in the context of the variable we are trying to evaluate.
Since x = 3 is found first, the value of x is 3.

Example 2:

Input: expression = "(let x 3 x 2 x)"
Output: 2
Explanation: Assignment in let statements is processed sequentially.

Example 3:

Input: expression = "(let x 1 y 2 x (add x y) (add x y))"
Output: 5
Explanation: The first (add x y) evaluates as 3, and is assigned to x.
The second (add x y) evaluates as 3+2 = 5.

Constraints:

1 <= expression.length <= 2000
There are no leading or trailing spaces in expression.
All tokens are separated by a single space in expression.
The answer and all intermediate calculations of that answer are guaranteed to fit in a 32-bit integer.
The expression is guaranteed to be legal and evaluate to an integer.

Step 01

Brute Force Baseline

Problem summary: You are given a string expression representing a Lisp-like expression to return the integer value of. The syntax for these expressions is given as follows. An expression is either an integer, let expression, add expression, mult expression, or an assigned variable. Expressions always evaluate to a single integer. (An integer could be positive or negative.) A let expression takes the form "(let v1 e1 v2 e2 ... vn en expr)", where let is always the string "let", then there are one or more pairs of alternating variables and expressions, meaning that the first variable v1 is assigned the value of the expression e1, the second variable v2 is assigned the value of the expression e2, and so on sequentially; and then the value of this let expression is the value of the expression expr. An add expression takes the form "(add e1 e2)" where add is always the string "add", there are always two

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Hash Map · Stack

Example 1

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

Example 2

"(let x 3 x 2 x)"

Example 3

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

Core Insight

What unlocks the optimal approach

* If the expression starts with a digit or '-', it's an integer: return it. * If the expression starts with a letter, it's a variable. Recall it by checking the current scope in reverse order. * Otherwise, group the tokens (variables or expressions) within this expression by counting the "balance" `bal` of the occurrences of `'('` minus the number of occurrences of `')'`. When the balance is zero, we have ended a token. For example, `(add 1 (add 2 3))` should have tokens `'1'` and `'(add 2 3)'`. * For add and mult expressions, evaluate each token and return the addition or multiplication of them. * For let expressions, evaluate each expression sequentially and assign it to the variable in the current scope, then return the evaluation of the final expression.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #736: Parse Lisp Expression
class Solution {
    private int i;
    private String expr;
    private Map<String, Deque<Integer>> scope = new HashMap<>();

    public int evaluate(String expression) {
        expr = expression;
        return eval();
    }

    private int eval() {
        char c = expr.charAt(i);
        if (c != '(') {
            return Character.isLowerCase(c) ? scope.get(parseVar()).peekLast() : parseInt();
        }
        ++i;
        c = expr.charAt(i);
        int ans = 0;
        if (c == 'l') {
            i += 4;
            List<String> vars = new ArrayList<>();
            while (true) {
                String var = parseVar();
                if (expr.charAt(i) == ')') {
                    ans = scope.get(var).peekLast();
                    break;
                }
                vars.add(var);
                ++i;
                scope.computeIfAbsent(var, k -> new ArrayDeque<>()).offer(eval());
                ++i;
                if (!Character.isLowerCase(expr.charAt(i))) {
                    ans = eval();
                    break;
                }
            }
            for (String v : vars) {
                scope.get(v).pollLast();
            }
        } else {
            boolean add = c == 'a';
            i += add ? 4 : 5;
            int a = eval();
            ++i;
            int b = eval();
            ans = add ? a + b : a * b;
        }
        ++i;
        return ans;
    }

    private String parseVar() {
        int j = i;
        while (i < expr.length() && expr.charAt(i) != ' ' && expr.charAt(i) != ')') {
            ++i;
        }
        return expr.substring(j, i);
    }

    private int parseInt() {
        int sign = 1;
        if (expr.charAt(i) == '-') {
            sign = -1;
            ++i;
        }
        int v = 0;
        while (i < expr.length() && Character.isDigit(expr.charAt(i))) {
            v = v * 10 + (expr.charAt(i) - '0');
            ++i;
        }
        return sign * v;
    }
}

// Accepted solution for LeetCode #736: Parse Lisp Expression
func evaluate(expression string) int {
	i, n := 0, len(expression)
	scope := map[string][]int{}

	parseVar := func() string {
		j := i
		for ; i < n && expression[i] != ' ' && expression[i] != ')'; i++ {
		}
		return expression[j:i]
	}

	parseInt := func() int {
		sign, v := 1, 0
		if expression[i] == '-' {
			sign = -1
			i++
		}
		for ; i < n && expression[i] >= '0' && expression[i] <= '9'; i++ {
			v = (v * 10) + int(expression[i]-'0')
		}
		return sign * v
	}

	var eval func() int
	eval = func() int {
		if expression[i] != '(' {
			if unicode.IsLower(rune(expression[i])) {
				t := scope[parseVar()]
				return t[len(t)-1]
			}
			return parseInt()
		}
		i++
		ans := 0
		if expression[i] == 'l' {
			i += 4
			vars := []string{}
			for {
				v := parseVar()
				if expression[i] == ')' {
					t := scope[v]
					ans = t[len(t)-1]
					break
				}
				i++
				vars = append(vars, v)
				scope[v] = append(scope[v], eval())
				i++
				if !unicode.IsLower(rune(expression[i])) {
					ans = eval()
					break
				}
			}
			for _, v := range vars {
				scope[v] = scope[v][:len(scope[v])-1]
			}
		} else {
			add := expression[i] == 'a'
			if add {
				i += 4
			} else {
				i += 5
			}
			a := eval()
			i++
			b := eval()
			if add {
				ans = a + b
			} else {
				ans = a * b
			}
		}
		i++
		return ans
	}
	return eval()
}

# Accepted solution for LeetCode #736: Parse Lisp Expression
class Solution:
    def evaluate(self, expression: str) -> int:
        def parseVar():
            nonlocal i
            j = i
            while i < n and expression[i] not in " )":
                i += 1
            return expression[j:i]

        def parseInt():
            nonlocal i
            sign, v = 1, 0
            if expression[i] == "-":
                sign = -1
                i += 1
            while i < n and expression[i].isdigit():
                v = v * 10 + int(expression[i])
                i += 1
            return sign * v

        def eval():
            nonlocal i
            if expression[i] != "(":
                return scope[parseVar()][-1] if expression[i].islower() else parseInt()
            i += 1
            if expression[i] == "l":
                i += 4
                vars = []
                while 1:
                    var = parseVar()
                    if expression[i] == ")":
                        ans = scope[var][-1]
                        break
                    vars.append(var)
                    i += 1
                    scope[var].append(eval())
                    i += 1
                    if not expression[i].islower():
                        ans = eval()
                        break
                for v in vars:
                    scope[v].pop()
            else:
                add = expression[i] == "a"
                i += 4 if add else 5
                a = eval()
                i += 1
                b = eval()
                ans = a + b if add else a * b
            i += 1
            return ans

        i, n = 0, len(expression)
        scope = defaultdict(list)
        return eval()

// Accepted solution for LeetCode #736: Parse Lisp Expression
struct Solution;

use std::collections::HashMap;
use std::iter::Peekable;
use std::str::Chars;
use std::vec::IntoIter;

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum Tok {
    Var(usize),
    Num(i32),
    Op(char),
}

use Tok::*;

impl Solution {
    fn evaluate(expression: String) -> i32 {
        let mut it = expression.chars().peekable();
        let mut symbols: HashMap<String, usize> = HashMap::new();
        let tokens = Self::parse_tokens(&mut it, &mut symbols);
        let mut it = tokens.into_iter().peekable();
        let k = symbols.len();
        let mut stacks = vec![vec![]; k];
        Self::eval_expr(&mut it, &mut stacks).unwrap()
    }

    fn eval_expr(it: &mut Peekable<IntoIter<Tok>>, stacks: &mut Vec<Vec<i32>>) -> Option<i32> {
        let tok = it.next().unwrap();
        match tok {
            Op('(') => {
                let res = Self::eval_complex_expr(it, stacks).unwrap();
                let close = it.next().unwrap();
                if close != Op(')') {
                    panic!();
                }
                Some(res)
            }
            Var(id) => Some(stacks[id].last().copied().unwrap()),
            Num(x) => Some(x),
            _ => {
                panic!()
            }
        }
    }

    fn eval_complex_expr(
        it: &mut Peekable<IntoIter<Tok>>,
        stacks: &mut Vec<Vec<i32>>,
    ) -> Option<i32> {
        let tok = it.next().unwrap();
        match tok {
            Op('=') => {
                let mut locals = vec![];
                let mut ambiguous: Option<i32> = None;
                while let Some(Var(_)) = it.peek() {
                    if let Some(Var(id)) = it.next() {
                        if let Some(Op(')')) = it.peek() {
                            let val = stacks[id].last().copied().unwrap();
                            ambiguous = Some(val);
                            break;
                        } else {
                            let expr = Self::eval_expr(it, stacks).unwrap();
                            stacks[id].push(expr);
                            locals.push(id);
                        }
                    } else {
                        panic!();
                    }
                }
                let res = if let Some(val) = ambiguous {
                    val
                } else {
                    Self::eval_expr(it, stacks).unwrap()
                };
                for id in locals {
                    stacks[id].pop().unwrap();
                }
                Some(res)
            }
            Op('+') => {
                Some(Self::eval_expr(it, stacks).unwrap() + Self::eval_expr(it, stacks).unwrap())
            }
            Op('*') => {
                Some(Self::eval_expr(it, stacks).unwrap() * Self::eval_expr(it, stacks).unwrap())
            }
            _ => panic!(),
        }
    }

    fn parse_tokens(it: &mut Peekable<Chars>, symbols: &mut HashMap<String, usize>) -> Vec<Tok> {
        let mut res = vec![];
        while let Some(c) = it.next() {
            match c {
                '(' | ')' => res.push(Tok::Op(c)),
                '-' => {
                    let mut x = 0;
                    while let Some(next_c) = it.peek() {
                        if next_c.is_numeric() {
                            x *= 10;
                            x += (it.next().unwrap() as u8 - b'0') as i32;
                        } else {
                            break;
                        }
                    }
                    res.push(Tok::Num(-x));
                }
                '0'..='9' => {
                    let mut x = (c as u8 - b'0') as i32;
                    while let Some(next_c) = it.peek() {
                        if next_c.is_numeric() {
                            x *= 10;
                            x += (it.next().unwrap() as u8 - b'0') as i32;
                        } else {
                            break;
                        }
                    }
                    res.push(Tok::Num(x));
                }
                'a'..='z' => {
                    let mut s = "".to_string();
                    s.push(c);
                    while let Some(next_c) = it.peek() {
                        if next_c.is_alphanumeric() {
                            s.push(it.next().unwrap());
                        } else {
                            break;
                        }
                    }
                    match s.as_str() {
                        "let" => res.push(Tok::Op('=')),
                        "mult" => res.push(Tok::Op('*')),
                        "add" => res.push(Tok::Op('+')),
                        _ => {
                            let size = symbols.len();
                            let id = *symbols.entry(s).or_insert(size);
                            res.push(Tok::Var(id));
                        }
                    }
                }
                ' ' => {}
                _ => panic!(),
            }
        }
        res
    }
}

#[test]
fn test() {
    let expression = "(add 1 2)".to_string();
    let res = 3;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(mult 3 (add 2 3))".to_string();
    let res = 15;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(let x 2 (mult x 5))".to_string();
    let res = 10;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))".to_string();
    let res = 14;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(let x 3 x 2 x)".to_string();
    let res = 2;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(let x 1 y 2 x (add x y) (add x y))".to_string();
    let res = 5;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(let x 2 (add (let x 3 (let x 4 x)) x))".to_string();
    let res = 6;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(let a1 3 b2 (add a1 1) b2)".to_string();
    let res = 4;
    assert_eq!(Solution::evaluate(expression), res);
    let expression = "(let x 7 -12)".to_string();
    let res = -12;
    assert_eq!(Solution::evaluate(expression), res);
}

// Accepted solution for LeetCode #736: Parse Lisp Expression
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #736: Parse Lisp Expression
// class Solution {
//     private int i;
//     private String expr;
//     private Map<String, Deque<Integer>> scope = new HashMap<>();
// 
//     public int evaluate(String expression) {
//         expr = expression;
//         return eval();
//     }
// 
//     private int eval() {
//         char c = expr.charAt(i);
//         if (c != '(') {
//             return Character.isLowerCase(c) ? scope.get(parseVar()).peekLast() : parseInt();
//         }
//         ++i;
//         c = expr.charAt(i);
//         int ans = 0;
//         if (c == 'l') {
//             i += 4;
//             List<String> vars = new ArrayList<>();
//             while (true) {
//                 String var = parseVar();
//                 if (expr.charAt(i) == ')') {
//                     ans = scope.get(var).peekLast();
//                     break;
//                 }
//                 vars.add(var);
//                 ++i;
//                 scope.computeIfAbsent(var, k -> new ArrayDeque<>()).offer(eval());
//                 ++i;
//                 if (!Character.isLowerCase(expr.charAt(i))) {
//                     ans = eval();
//                     break;
//                 }
//             }
//             for (String v : vars) {
//                 scope.get(v).pollLast();
//             }
//         } else {
//             boolean add = c == 'a';
//             i += add ? 4 : 5;
//             int a = eval();
//             ++i;
//             int b = eval();
//             ans = add ? a + b : a * b;
//         }
//         ++i;
//         return ans;
//     }
// 
//     private String parseVar() {
//         int j = i;
//         while (i < expr.length() && expr.charAt(i) != ' ' && expr.charAt(i) != ')') {
//             ++i;
//         }
//         return expr.substring(j, i);
//     }
// 
//     private int parseInt() {
//         int sign = 1;
//         if (expr.charAt(i) == '-') {
//             sign = -1;
//             ++i;
//         }
//         int v = 0;
//         while (i < expr.length() && Character.isDigit(expr.charAt(i))) {
//             v = v * 10 + (expr.charAt(i) - '0');
//             ++i;
//         }
//         return sign * v;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.

MONOTONIC STACK

O(n) time

O(n) space

Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.

Shortcut: Each element pushed once + popped once → O(n) amortized. The inner while-loop does not make it O(n²).

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Breaking monotonic invariant

Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.

Usually fails on: Indices point to blocked elements and outputs shift.

Fix: Pop while invariant is violated before pushing current element.