Skip to main content
Talentd

Parse Lisp Expression - Solution & Explanation

HardHash TableStringStackRecursion14 min readAsked at: Apple, Google, Affirm +1
Practice this 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 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 expressions e1, e2 and the result is the addition of the evaluation of e1 and the evaluation of e2.
  • A mult expression takes the form "(mult e1 e2)" where mult is always the string "mult", there are always two expressions e1, e2 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.

Approach Overview

Problem Overview: You receive a Lisp-style expression containing add, mult, and let operations. Variables can be assigned values and reused within nested scopes. The goal is to parse the string and evaluate the final integer result while respecting variable scope and nested parentheses.

Approach 1: Recursive Parsing (O(n) time, O(n) space)

This approach treats the expression as a recursive structure. Each time you encounter (, you parse the operation (add, mult, or let) and recursively evaluate its arguments. A hash map stores variable bindings for the current scope, and nested calls receive a copied or layered environment so inner assignments do not leak outward. For add and mult, recursively evaluate two operands. For let, iterate through variable-value pairs and update the environment before evaluating the final expression. Each character in the string is processed once, giving O(n) time complexity. The recursion stack and variable maps contribute O(n) space in the worst case when deeply nested expressions appear. This method maps directly to the grammar of the expression and is often the cleanest way to reason about nested evaluation using recursion and hash tables.

Approach 2: Iterative Parsing with Stacks (O(n) time, O(n) space)

An iterative parser replaces recursion with explicit stacks. Scan the string character by character and push tokens onto a stack whenever you encounter parentheses or operands. When a closing parenthesis appears, pop tokens until the matching opening parenthesis, evaluate the subexpression, and push the result back onto the stack. A secondary structure tracks variable scopes created by let operations so assignments remain valid only inside the current expression block. This design mimics how compilers evaluate nested expressions using stacks. Each token is pushed and popped at most once, so the runtime remains O(n). Space usage is also O(n) due to stacks and scope maps. This approach is useful if you want full control over parsing without relying on recursion depth.

Recommended for interviews: Recursive parsing is usually expected because the nested structure of Lisp expressions naturally forms a recursive evaluation tree. Interviewers want to see that you can manage variable scope correctly using a hash map and evaluate expressions as you descend into parentheses. The stack-based parser demonstrates deeper understanding of interpreters and expression evaluation but takes more implementation effort.

Approach 1: Recursive Parsing

This approach uses a recursive function to evaluate the expression. It leverages the call stack to manage the scope of variables and interpret the expression inside-out. With every encountered sub-expression, the function evaluates and returns the result. It's well-suited for problems where the expression can be broken recursively.

This solution uses a recursive function eval_expr that processes a tokenized version of the input expression string. It maintains a scope using a dictionary, allowing nested variable bindings. The recursion allows processing of nested expressions, and each part of the expression (let, add, mult) is interpreted and computed recursively. Handling of parentheses ensures the correct parsing of expressions.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the length of the expression because we should parse each character at least once.
Space Complexity: O(n) in the worst case due to recursion stack and scope storage.

Try this approach in the editor β†’

Approach 2: Iterative Parsing with Stacks

This approach uses an iterative process with stacks to evaluate the expression. It processes tokens sequentially and uses multiple stacks to manage the current values, scopes, and operations, providing an efficient and clear way to manage nested and complex expressions.

The JavaScript solution employs a stack-based approach to manage parsing and interpretation iteratively because JavaScript handles iterables effectively through such mechanisms. Multiple stacks are used to maintain separate components, involving scopes (for variable state), operators (for the current operational context), and tokenStack (for parsed tokens and results). This approach achieves efficient parsing and allows handling nested scopes easily.

Code

JavaScriptC++

JavaScript

C++

Complexity

Time Complexity: O(n), where n is the length of the expression.
Space Complexity: O(n) for the stacks used in parsing.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Recursive Parsing

Time Complexity: O(n), where n is the length of the expression because we should parse each character at least once.
Space Complexity: O(n) in the worst case due to recursion stack and scope storage.

Iterative Parsing with Stacks

Time Complexity: O(n), where n is the length of the expression.
Space Complexity: O(n) for the stacks used in parsing.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive ParsingO(n)O(n)Best for interview settings and when the expression structure maps naturally to recursion.
Iterative Parsing with StacksO(n)O(n)Useful when avoiding recursion depth limits or implementing interpreter-style parsing.

Video Solution

θŠ±θŠ±ι…± LeetCode 736. Parse Lisp Expression - εˆ·ι’˜ζ‰Ύε·₯作 EP119 β€’ Hua Hua β€’ 6,745 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Parse Lisp Expression easy or hard?
Parse Lisp Expression is classified as a hard problem because it combines string parsing, recursion, and variable scope management. The challenge lies in correctly handling nested let expressions and ensuring variable values follow lexical scoping rules.
Parse Lisp Expression Python/Java solution
Python and Java implementations usually use recursive parsing with a dictionary or HashMap representing the current variable scope. The parser reads the operation, recursively evaluates operands, and handles let assignments before computing the final result. Both languages achieve O(n) time complexity.
How to solve Parse Lisp Expression in O(n)?
Parse the string once while evaluating expressions as soon as a complete subexpression is identified. Recursive parsing processes nested parentheses directly, while stack-based parsing evaluates tokens when encountering a closing parenthesis. Both strategies avoid repeated scans of the expression and maintain O(n) complexity.
What is the best approach for Parse Lisp Expression?
Recursive parsing is the most common solution. The expression naturally forms a tree where each parenthesis represents a nested operation, so recursion evaluates subexpressions cleanly. Using a hash map for variable scopes allows correct handling of let assignments. The solution runs in O(n) time and O(n) space.
Is Parse Lisp Expression asked at Google/Amazon/Meta?
Expression parsing and interpreter-style problems frequently appear in interviews at companies like Google and Meta. Variations of this problem test recursion, stack-based parsing, and scope handling. Understanding how to evaluate nested expressions and manage variable environments is the key skill being assessed.
What data structure is used in Parse Lisp Expression?
The main data structures are hash tables for variable bindings and either recursion or stacks for parsing nested expressions. Hash maps track variable values within the current scope, while stacks or recursive calls manage nested parentheses during evaluation.
What is the time complexity of Parse Lisp Expression?
Both common approaches run in O(n) time, where n is the length of the expression string. Each character or token is parsed once and evaluated once. Space complexity is also O(n) due to recursion depth, stacks, and variable scope storage.

Ready to solve this problem?

Practice Parse Lisp Expression with our built-in code editor and test cases.

Practice on FleetCode
Previous

Basic Calculator IV

Next

Number of Atoms