Parse Lisp Expression solution and explanation
Google
9 more videos on this problem
花花酱 LeetCode 736. Parse Lisp Expression - 刷题找工作 EP119Hua Hua · 19:40 · 6K views
LeetCode 736. Parse Lisp Expression Explanation and Solutionhappygirlzt · 12:29 · 3K views
LeetCode 736. Parse Lisp Expression 中文解释 Chinese Versionhappygirlzt · 12:34 · 915 views
Leetcode 736. Parse Lisp Expression - Weekly contest 60 prob 4 - PythonMohimenul Joaa · 18:32 · 552 views
736. Parse Lisp Expression (Leetcode Hard)Programming Live with Larry · 54:57 · 536 views
【每日一题】736. Parse Lisp Expression, 08/19/2019Huifeng Guan · 54:16 · 401 views
LeetCode #736: Parse Lisp Expression in Java | Brute Force vs Scoped Recursion - Compiler-Grade!!!Algo Ducky · 5:56 · 156 views
No Sound Leetcode 736: Parse Lisp ExpressionExtremeProgrammer · 4:32 · 52 views
LeetCode 736: Parse Lisp ExpressionAlitaCode · 29:59 · 41 views
LeetCode Problem #736 Parse Lisp Expression神戸万事屋 · 0:54 · 2 views
The problem
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 variablev1is assigned the value of the expressione1, the second variablev2is assigned the value of the expressione2, and so on sequentially; and then the value of this let expression is the value of the expressionexpr. - An add expression takes the form
"(add e1 e2)"where add is always the string"add", there are always two expressionse1,e2and the result is the addition of the evaluation ofe1and the evaluation ofe2. - A mult expression takes the form
"(mult e1 e2)"where mult is always the string"mult", there are always two expressionse1,e2and 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.
def evaluate(expression):
def eval_expr(tokens, index, scope):
if tokens[index] == 'let':
index += 1
while index < len(tokens) - 1:
if tokens[index].isalpha():
var = tokens[index]
index += 1
val, index = eval_expr(tokens, index, dict(scope)) if tokens[index] != '(' else eval_expr(tokens, index, dict(scope))
scope[var] = val
else:
break
return eval_expr(tokens, index, dict(scope))
elif tokens[index] == 'add':
x, index = eval_expr(tokens, index + 1, dict(scope))
y, index = eval_expr(tokens, index, dict(scope))
return x + y, index
elif tokens[index] == 'mult':
x, index = eval_expr(tokens, index + 1, dict(scope))
y, index = eval_expr(tokens, index, dict(scope))
return x * y, index
else:
return (int(tokens[index]) if tokens[index].isdigit() or tokens[index][0] == '-' else scope[tokens[index]]), index + 1
tokens = []
i = 0
while i < len(expression):
if expression[i] == ' ' or expression[i] == ')':
i += 1
continue
elif expression[i] == '(':
tokens.append(expression[i])
i += 1
else:
start = i
while i < len(expression) and expression[i] not in ' ()':
i += 1
tokens.append(expression[start:i])
continue
return eval_expr(tokens, 1, {})[0]import java.util.*;
public class Solution {
public int evaluate(String expression) {
return eval(new HashMap<>(), expression);
}
private int eval(Map<String, Integer> parent, String expression) {
Map<String, Integer> scope = new HashMap(parent);
if (expression.charAt(0) != '(') {
if (Character.isDigit(expression.charAt(0)) || expression.charAt(0) == '-')
return Integer.parseInt(expression);
return scope.get(expression);
}
List<String> tokens = parse(expression.substring(1, expression.length() - 1));
if (tokens.get(0).equals("let")) {
for (int i = 1; i < tokens.size() - 1; i += 2)
scope.put(tokens.get(i), eval(scope, tokens.get(i + 1)));
return eval(scope, tokens.get(tokens.size() - 1));
} else if (tokens.get(0).equals("add"))
return eval(scope, tokens.get(1)) + eval(scope, tokens.get(2));
else if (tokens.get(0).equals("mult"))
return eval(scope, tokens.get(1)) * eval(scope, tokens.get(2));
throw new RuntimeException("Unknown expression");
}
private List<String> parse(String str) {
List<String> res = new ArrayList<>();
int bal = 0;
StringBuilder sb = new StringBuilder();
for (String s : str.split(" ")) {
for (char c : s.toCharArray()) {
if (c == '(') bal++;
if (c == ')') bal--;
}
if (sb.length() > 0) sb.append(" ");
sb.append(s);
if (bal == 0) {
res.add(new String(sb));
sb = new StringBuilder();
}
}
if (sb.length() > 0) res.add(new String(sb));
return res;
}
}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.
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.
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.
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int evaluate(string expression) {
vector<unordered_map<string, int>> scopeStack;
scopeStack.push_back(unordered_map<string, int>{});
return evaluateExpression(expression, scopeStack);
}
private:
int evaluateExpression(const string &expr, vector<unordered_map<string, int>> &scopeStack) {
if (expr[0] != '(') {
return isalpha(expr[0]) ? scopeStack.back()[expr] : stoi(expr);
}
vector<string> tokens = tokenize(expr.substr(1, expr.length() - 2));
string operation = tokens[0];
if (operation == "let") {
int i = 1;
while (i + 2 < tokens.size()) {
scopeStack.back()[tokens[i]] = evaluateExpression(tokens[i + 1], scopeStack);
i += 2;
}
return evaluateExpression(tokens[i], scopeStack);
} else if (operation == "add") {
return evaluateExpression(tokens[1], scopeStack) + evaluateExpression(tokens[2], scopeStack);
} else if (operation == "mult") {
return evaluateExpression(tokens[1], scopeStack) * evaluateExpression(tokens[2], scopeStack);
}
return 0; // default case
}
vector<string> tokenize(const string &expr) {
vector<string> tokens;
int bal = 0;
string currentToken;
for (char c : expr) {
if (c == '(' || c == ')')
bal += (c == '(' ? 1 : -1);
else if (c == ' ' && bal == 0) {
tokens.push_back(currentToken);
currentToken.clear();
continue;
}
currentToken += c;
}
if (!currentToken.empty())
tokens.push_back(currentToken);
return tokens;
}
};function evaluate(expression) {
const scopeStack = [{}];
const tokenStack = [];
const opStack = [];
let i = 0;
while (i < expression.length) {
if (expression[i] === '(') {
opStack.push(++i);
scopeStack.push({ ...scopeStack[scopeStack.length - 1] });
} else if (expression[i] === ')') {
const start = opStack.pop();
const scope = scopeStack.pop();
const body = expression.substring(start, i);
const tokens = tokenize(body);
const result = execute(tokens, scope);
tokenStack.push(result);
i++;
} else if (expression[i] !== ' ') {
let start = i;
while (i < expression.length && expression[i] !== '(' && expression[i] !== ')') {
i++;
}
tokenStack.push(expression.substring(start, i));
} else {
i++;
}
}
function tokenize(input) {
return input.match(/\(|\)|[-]?[0-9]+|[a-z]+/g);
}
function execute(tokens, currentScope) {
const operation = tokens.shift();
if (operation === "let") {
let key = null;
for (let i = 0; i < tokens.length - 1; i++) {
if (i % 2 === 0) {
key = tokens[i];
} else {
const value = (tokens[i].match(/[-]?[0-9]+/) ?
+tokens[i] :
currentScope[tokens[i]] || +tokenStack.pop());
currentScope[key] = value;
}
}
return +tokenStack.pop();
} else if (operation === "add") {
return +tokenStack.pop() + +tokenStack.pop();
} else if (operation === "mult") {
return +tokenStack.pop() * +tokenStack.pop();
} else {
return currentScope[operation] || +operation;
}
}
return tokenStack.pop();
}This C++ solution uses a combination of iterative and recursive strategies with stacks to handle variable scope. It maintains a stack of scopes, updating them as expressions are parsed. The tokenize function processes the expression string into tokens, respecting the balance of parentheses. This approach allows the handling of nested expressions naturally by utilizing C++ vector and unordered_map for efficient scope and state management.
Time Complexity: O(n), where n is the length of the expression.
Space Complexity: O(n) due to the stacks and scope replication.
Approach 3: Default Approach
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()
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Parsing | Time Complexity: O(n), where n is the length of the expression because we should parse each character at least once. |
| Iterative Parsing with Stacks | Time Complexity: O(n), where n is the length of the expression. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Parsing | O(n) | O(n) | Best for interview settings and when the expression structure maps naturally to recursion. |
| Iterative Parsing with Stacks | O(n) | O(n) | Useful when avoiding recursion depth limits or implementing interpreter-style parsing. |
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.