736. Parse Lisp Expression
Problem Description
This problem asks you to evaluate a string expression written in a Lisp-like syntax and return its integer value.
The expression can be one of the following types:
-
Integer: A simple integer value (positive or negative)
-
Variable: A variable name that starts with a lowercase letter followed by zero or more lowercase letters or digits
-
Let Expression: Has the format
"(let v1 e1 v2 e2 ... vn en expr)"
where:let
is the keywordv1, v2, ..., vn
are variable namese1, e2, ..., en
are expressions whose values get assigned to the corresponding variablesexpr
is the final expression whose value becomes the result of the entire let expression- Variables are assigned sequentially, and each assignment can use previously assigned variables in the same let expression
-
Add Expression: Has the format
"(add e1 e2)"
where:add
is the keyworde1
ande2
are expressions to be evaluated- The result is the sum of the evaluated values of
e1
ande2
-
Mult Expression: Has the format
"(mult e1 e2)"
where:mult
is the keyworde1
ande2
are expressions to be evaluated- The result is the product of the evaluated values of
e1
ande2
Scope Rules:
- When evaluating a variable, the innermost scope (closest enclosing parentheses) is checked first for the variable's value
- If not found, outer scopes are checked sequentially
- Variables defined in a let expression are only valid within that expression's scope
Constraints:
- The keywords
"add"
,"let"
, and"mult"
are reserved and will never be used as variable names - All expressions are guaranteed to be valid
For example, "(let x 2 (mult x (let x 3 y 4 (add x y))))"
would evaluate to 14
because:
- Outer
x
is assigned2
- Inner let assigns
x = 3
andy = 4
(add x y)
uses the inner scope values:3 + 4 = 7
(mult x 7)
uses the outer scopex = 2
:2 * 7 = 14
Intuition
The key insight is that this problem is essentially asking us to build an interpreter for a simple programming language. When we see nested parentheses and variable scoping, we should think about recursive evaluation - each expression can contain other expressions, so we need to evaluate them from the inside out.
The natural approach is to parse and evaluate the expression as we go through it character by character. When we encounter an opening parenthesis (
, we know we're entering a new expression that needs to be evaluated recursively. The type of expression is determined by the keyword that follows (let
, add
, or mult
).
For handling variable scopes, we need a data structure that can track multiple values for the same variable name at different scope levels. A dictionary mapping variable names to a stack of values works perfectly here. When we enter a let
expression and assign a value to a variable, we push the new value onto that variable's stack. When we exit the let
expression, we pop the value off, effectively restoring the previous scope's value.
The parsing strategy follows these patterns:
- Variables: Start with a lowercase letter, so we read characters until we hit a space or closing parenthesis
- Integers: May start with a minus sign, followed by digits
- Expressions: Always start with
(
and we recursively evaluate based on the keyword
The recursive nature of eval()
mirrors the recursive structure of the expressions themselves. Each call to eval()
handles one complete expression and returns its integer value. For let
expressions, we need to carefully manage the scope by tracking which variables we've modified so we can restore them after evaluation.
The pointer-based parsing (using index i
to track our position) allows us to efficiently move through the string without creating substrings unnecessarily, and the nonlocal declaration lets nested functions modify this shared parsing position.
Solution Approach
The solution uses a recursive parsing and evaluation approach with a global index pointer to track the current position in the expression string.
Data Structures:
scope
: Adefaultdict(list)
where each key is a variable name and the value is a stack (list) of values. This handles nested scopes by pushing/popping values.i
: A global index pointer to track the current parsing positionn
: The length of the expression string
Helper Functions:
-
parseVar()
: Extracts a variable name starting from the current position- Records the starting position
j = i
- Advances
i
until we hit a space or closing parenthesis - Returns the substring
expression[j:i]
as the variable name
- Records the starting position
-
parseInt()
: Parses an integer value- Checks for negative sign and sets
sign = -1
if present - Accumulates digits using
v = v * 10 + int(expression[i])
- Returns
sign * v
as the final integer
- Checks for negative sign and sets
-
eval()
: The main recursive evaluation function- Base cases (no opening parenthesis):
- If starts with lowercase letter → it's a variable, return
scope[parseVar()][-1]
(top of the stack) - Otherwise → it's an integer, return
parseInt()
- If starts with lowercase letter → it's a variable, return
- Recursive cases (starts with
(
):- Skip the opening parenthesis by incrementing
i
- Check the first character to determine expression type:
let
expressions (starts with 'l'):- Skip "let " by advancing
i += 4
- Create
vars
list to track variables modified in this scope - Loop to parse variable-value pairs:
- Parse variable name using
parseVar()
- If next character is
)
, this variable is actually the final expression to evaluate - Otherwise, append variable to
vars
list - Recursively evaluate the value expression with
eval()
- Push the value onto the variable's stack:
scope[var].append(eval())
- Check if next token is a variable (lowercase letter) to continue pairing
- If not, evaluate the final expression
- Parse variable name using
- Clean up scope by popping all modified variables:
scope[v].pop()
for eachv
invars
add
ormult
expressions:-
Determine operation type:
add = expression[i] == "a"
-
Skip the operation keyword ("add " is 4 chars, "mult " is 5 chars)
-
Recursively evaluate first operand:
a = eval()
-
Skip the space between operands
-
Recursively evaluate second operand:
b = eval()
-
Calculate result:
ans = a + b
for add,ans = a * b
for mult -
Skip the closing parenthesis before returning
- Skip the opening parenthesis by incrementing
- Base cases (no opening parenthesis):
Execution Flow:
- Initialize
i = 0
,n = len(expression)
, and emptyscope
- Call
eval()
which recursively processes the entire expression - The index
i
automatically advances as we parse, shared across all function calls vianonlocal
- Each recursive call to
eval()
returns an integer value - The scope stack ensures variables are properly scoped and restored after each
let
expression
The elegance of this solution lies in how the recursive structure of the code mirrors the recursive structure of the expressions, and how the stack-based scope management naturally handles the nested variable scoping rules.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's trace through the expression "(let x 2 (add x 3))"
step by step:
Initial State:
expression = "(let x 2 (add x 3))"
i = 0
,scope = {}
(empty)
Step 1: First eval() call
expression[0] = '('
→ Enter recursive casei = 1
(skip opening parenthesis)expression[1] = 'l'
→ This is alet
expressioni = 5
(skip "let ")
Step 2: Parse first variable-value pair
- Call
parseVar()
at position 5:j = 5
expression[5] = 'x'
→ valid variable characteri = 6
expression[6] = ' '
→ stop parsing- Return
"x"
var = "x"
, add tovars = ["x"]
i = 7
(skip space)- Call
eval()
to get value forx
:expression[7] = '2'
→ It's an integer- Call
parseInt()
: returns2
scope["x"].append(2)
→scope = {"x": [2]}
i = 8
(after parsing "2")
Step 3: Parse final expression
i = 9
(skip space)expression[9] = '('
→ Not a variable, so this is the final expression- Call
eval()
for"(add x 3)"
:expression[9] = '('
→ Enter recursive casei = 10
(skip opening parenthesis)expression[10] = 'a'
→ This is anadd
expressioni = 14
(skip "add ")
Step 4: Evaluate add expression
- First operand - call
eval()
:expression[14] = 'x'
→ It's a variable- Call
parseVar()
: returns"x"
- Look up
scope["x"][-1] = 2
- Return
2
i = 16
(skip "x ")- Second operand - call
eval()
:expression[16] = '3'
→ It's an integer- Call
parseInt()
: returns3
i = 17
(after parsing "3")- Calculate:
ans = 2 + 3 = 5
i = 18
(skip closing parenthesis)- Return
5
Step 5: Clean up let expression
- Back in the
let
expression,ans = 5
- Pop modified variables:
scope["x"].pop()
→scope = {"x": []}
i = 19
(skip closing parenthesis)- Return
5
Final Result: 5
The key points illustrated:
- The index
i
advances as we parse, shared across all recursive calls - Variables are pushed onto scope stacks when assigned in
let
- Variable lookups use the top of the stack (
scope[var][-1]
) - Scope cleanup happens after evaluating the final expression by popping all modified variables
- Each
eval()
call handles one complete expression and returns its integer value
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def evaluate(self, expression: str) -> int:
5 """
6 Evaluates a Lisp-like expression and returns the result.
7 Supports let, add, and mult operations with variable scoping.
8 """
9
10 def parse_variable():
11 """Parse a variable name from the current position."""
12 nonlocal index
13 start = index
14 # Continue until we hit a space or closing parenthesis
15 while index < length and expression[index] not in " )":
16 index += 1
17 return expression[start:index]
18
19 def parse_integer():
20 """Parse an integer value from the current position."""
21 nonlocal index
22 sign = 1
23 value = 0
24
25 # Handle negative numbers
26 if expression[index] == "-":
27 sign = -1
28 index += 1
29
30 # Build the integer digit by digit
31 while index < length and expression[index].isdigit():
32 value = value * 10 + int(expression[index])
33 index += 1
34
35 return sign * value
36
37 def evaluate_expression():
38 """Recursively evaluate the expression from the current position."""
39 nonlocal index
40
41 # Base cases: not an expression (either variable or integer)
42 if expression[index] != "(":
43 if expression[index].islower():
44 # It's a variable, return its current value from scope
45 var_name = parse_variable()
46 return scope[var_name][-1]
47 else:
48 # It's an integer literal
49 return parse_integer()
50
51 # Skip opening parenthesis
52 index += 1
53
54 # Handle 'let' expression
55 if expression[index] == "l":
56 # Skip "let " (4 characters)
57 index += 4
58 variables_assigned = []
59
60 while True:
61 var_name = parse_variable()
62
63 # Check if this is the final expression (no assignment)
64 if expression[index] == ")":
65 # Return the value of the variable
66 result = scope[var_name][-1]
67 break
68
69 # This variable gets assigned a value
70 variables_assigned.append(var_name)
71 index += 1 # Skip space
72
73 # Evaluate the value to assign
74 scope[var_name].append(evaluate_expression())
75 index += 1 # Skip space
76
77 # Check if next token is not a variable (final expression)
78 if not expression[index].islower():
79 result = evaluate_expression()
80 break
81
82 # Clean up scope - remove temporary variable bindings
83 for var in variables_assigned:
84 scope[var].pop()
85
86 # Handle 'add' or 'mult' expression
87 else:
88 is_addition = expression[index] == "a"
89 # Skip "add " (4 chars) or "mult " (5 chars)
90 index += 4 if is_addition else 5
91
92 # Evaluate first operand
93 operand1 = evaluate_expression()
94 index += 1 # Skip space
95
96 # Evaluate second operand
97 operand2 = evaluate_expression()
98
99 # Perform the operation
100 result = operand1 + operand2 if is_addition else operand1 * operand2
101
102 # Skip closing parenthesis
103 index += 1
104 return result
105
106 # Initialize parsing state
107 index = 0
108 length = len(expression)
109 # Use defaultdict to maintain variable scope stack
110 scope = defaultdict(list)
111
112 # Start evaluation
113 return evaluate_expression()
114
1class Solution {
2 // Current position in the expression string
3 private int currentIndex;
4 // The expression string to evaluate
5 private String expression;
6 // Variable scope map: variable name -> stack of values (for nested scopes)
7 private Map<String, Deque<Integer>> variableScope = new HashMap<>();
8
9 /**
10 * Main entry point to evaluate a Lisp-like expression
11 * @param expression The expression string to evaluate
12 * @return The integer result of the expression
13 */
14 public int evaluate(String expression) {
15 this.expression = expression;
16 this.currentIndex = 0;
17 return evaluateExpression();
18 }
19
20 /**
21 * Recursively evaluates an expression starting from current index
22 * @return The integer value of the evaluated expression
23 */
24 private int evaluateExpression() {
25 char currentChar = expression.charAt(currentIndex);
26
27 // If not starting with '(', it's either a variable or a number
28 if (currentChar != '(') {
29 if (Character.isLowerCase(currentChar)) {
30 // It's a variable - get its current value from scope
31 String variableName = parseVariable();
32 return variableScope.get(variableName).peekLast();
33 } else {
34 // It's a number - parse and return it
35 return parseInteger();
36 }
37 }
38
39 // Skip the opening parenthesis '('
40 currentIndex++;
41 currentChar = expression.charAt(currentIndex);
42 int result = 0;
43
44 // Check the operation type
45 if (currentChar == 'l') {
46 // Handle 'let' expression
47 currentIndex += 4; // Skip "let "
48 List<String> declaredVariables = new ArrayList<>();
49
50 while (true) {
51 String variable = parseVariable();
52
53 // Check if this is the final expression (no assignment)
54 if (expression.charAt(currentIndex) == ')') {
55 result = variableScope.get(variable).peekLast();
56 break;
57 }
58
59 // Store variable for later cleanup
60 declaredVariables.add(variable);
61 currentIndex++; // Skip space
62
63 // Evaluate the value and push to variable's scope stack
64 variableScope.computeIfAbsent(variable, k -> new ArrayDeque<>())
65 .offer(evaluateExpression());
66 currentIndex++; // Skip space after value
67
68 // Check if next is the final expression (not a variable declaration)
69 if (!Character.isLowerCase(expression.charAt(currentIndex))) {
70 result = evaluateExpression();
71 break;
72 }
73 }
74
75 // Clean up: remove values from scope for all declared variables
76 for (String var : declaredVariables) {
77 variableScope.get(var).pollLast();
78 }
79 } else {
80 // Handle 'add' or 'mult' expression
81 boolean isAddition = (currentChar == 'a');
82 currentIndex += isAddition ? 4 : 5; // Skip "add " or "mult "
83
84 // Evaluate first operand
85 int firstOperand = evaluateExpression();
86 currentIndex++; // Skip space
87
88 // Evaluate second operand
89 int secondOperand = evaluateExpression();
90
91 // Calculate result based on operation
92 result = isAddition ? firstOperand + secondOperand : firstOperand * secondOperand;
93 }
94
95 // Skip the closing parenthesis ')'
96 currentIndex++;
97 return result;
98 }
99
100 /**
101 * Parses a variable name from the current position
102 * @return The variable name as a string
103 */
104 private String parseVariable() {
105 int startIndex = currentIndex;
106
107 // Continue until we hit a space or closing parenthesis
108 while (currentIndex < expression.length() &&
109 expression.charAt(currentIndex) != ' ' &&
110 expression.charAt(currentIndex) != ')') {
111 currentIndex++;
112 }
113
114 return expression.substring(startIndex, currentIndex);
115 }
116
117 /**
118 * Parses an integer from the current position
119 * @return The parsed integer value
120 */
121 private int parseInteger() {
122 int sign = 1;
123
124 // Handle negative numbers
125 if (expression.charAt(currentIndex) == '-') {
126 sign = -1;
127 currentIndex++;
128 }
129
130 int value = 0;
131 // Parse digits
132 while (currentIndex < expression.length() &&
133 Character.isDigit(expression.charAt(currentIndex))) {
134 value = value * 10 + (expression.charAt(currentIndex) - '0');
135 currentIndex++;
136 }
137
138 return sign * value;
139 }
140}
141
1class Solution {
2public:
3 int currentIndex = 0; // Current position in the expression string
4 string expression; // The expression string to evaluate
5 unordered_map<string, vector<int>> variableScope; // Variable scope stack (variable name -> list of values)
6
7 int evaluate(string expression) {
8 this->expression = expression;
9 currentIndex = 0;
10 return evaluateExpression();
11 }
12
13private:
14 // Main recursive evaluation function
15 int evaluateExpression() {
16 // If not starting with '(', it's either a variable or an integer
17 if (expression[currentIndex] != '(') {
18 // Check if it's a variable (starts with lowercase letter)
19 if (islower(expression[currentIndex])) {
20 string varName = parseVariable();
21 return variableScope[varName].back(); // Return the most recent value
22 }
23 // Otherwise it's an integer
24 return parseInteger();
25 }
26
27 int result = 0;
28 currentIndex++; // Skip opening '('
29
30 // Check the operation type
31 if (expression[currentIndex] == 'l') { // "let" expression
32 currentIndex += 4; // Skip "let "
33 vector<string> declaredVariables; // Track variables declared in this scope
34
35 // Process variable assignments and final expression
36 while (true) {
37 string variable = parseVariable();
38
39 // If we hit ')', this variable is actually the final expression result
40 if (expression[currentIndex] == ')') {
41 result = variableScope[variable].back();
42 break;
43 }
44
45 currentIndex++; // Skip space after variable name
46 declaredVariables.push_back(variable);
47
48 // Evaluate and assign value to variable
49 variableScope[variable].push_back(evaluateExpression());
50 currentIndex++; // Skip space after value
51
52 // Check if next is the final expression (not a variable assignment)
53 if (!islower(expression[currentIndex])) {
54 result = evaluateExpression();
55 break;
56 }
57 }
58
59 // Clean up scope - remove variables declared in this let block
60 for (const string& var : declaredVariables) {
61 variableScope[var].pop_back();
62 }
63 }
64 else { // "add" or "mult" expression
65 bool isAddition = (expression[currentIndex] == 'a');
66 currentIndex += isAddition ? 4 : 5; // Skip "add " or "mult "
67
68 // Evaluate first operand
69 int firstOperand = evaluateExpression();
70 currentIndex++; // Skip space between operands
71
72 // Evaluate second operand
73 int secondOperand = evaluateExpression();
74
75 // Perform the operation
76 result = isAddition ? (firstOperand + secondOperand) : (firstOperand * secondOperand);
77 }
78
79 currentIndex++; // Skip closing ')'
80 return result;
81 }
82
83 // Parse a variable name from current position
84 string parseVariable() {
85 int startIndex = currentIndex;
86 // Continue until we hit a space or closing parenthesis
87 while (currentIndex < expression.size() &&
88 expression[currentIndex] != ' ' &&
89 expression[currentIndex] != ')') {
90 currentIndex++;
91 }
92 return expression.substr(startIndex, currentIndex - startIndex);
93 }
94
95 // Parse an integer from current position
96 int parseInteger() {
97 int sign = 1;
98 int value = 0;
99
100 // Handle negative numbers
101 if (expression[currentIndex] == '-') {
102 sign = -1;
103 currentIndex++;
104 }
105
106 // Parse digits
107 while (currentIndex < expression.size() &&
108 expression[currentIndex] >= '0' &&
109 expression[currentIndex] <= '9') {
110 value = value * 10 + (expression[currentIndex] - '0');
111 currentIndex++;
112 }
113
114 return sign * value;
115 }
116};
117
1let currentIndex: number = 0; // Current position in the expression string
2let expression: string = ""; // The expression string to evaluate
3let variableScope: Map<string, number[]> = new Map(); // Variable scope stack (variable name -> list of values)
4
5function evaluate(expr: string): number {
6 expression = expr;
7 currentIndex = 0;
8 variableScope = new Map();
9 return evaluateExpression();
10}
11
12// Main recursive evaluation function
13function evaluateExpression(): number {
14 // If not starting with '(', it's either a variable or an integer
15 if (expression[currentIndex] !== '(') {
16 // Check if it's a variable (starts with lowercase letter)
17 if (isLowerCase(expression[currentIndex])) {
18 const varName = parseVariable();
19 const values = variableScope.get(varName);
20 return values ? values[values.length - 1] : 0; // Return the most recent value
21 }
22 // Otherwise it's an integer
23 return parseInteger();
24 }
25
26 let result = 0;
27 currentIndex++; // Skip opening '('
28
29 // Check the operation type
30 if (expression[currentIndex] === 'l') { // "let" expression
31 currentIndex += 4; // Skip "let "
32 const declaredVariables: string[] = []; // Track variables declared in this scope
33
34 // Process variable assignments and final expression
35 while (true) {
36 const variable = parseVariable();
37
38 // If we hit ')', this variable is actually the final expression result
39 if (expression[currentIndex] === ')') {
40 const values = variableScope.get(variable);
41 result = values ? values[values.length - 1] : 0;
42 break;
43 }
44
45 currentIndex++; // Skip space after variable name
46 declaredVariables.push(variable);
47
48 // Evaluate and assign value to variable
49 const value = evaluateExpression();
50 if (!variableScope.has(variable)) {
51 variableScope.set(variable, []);
52 }
53 variableScope.get(variable)!.push(value);
54 currentIndex++; // Skip space after value
55
56 // Check if next is the final expression (not a variable assignment)
57 if (!isLowerCase(expression[currentIndex])) {
58 result = evaluateExpression();
59 break;
60 }
61 }
62
63 // Clean up scope - remove variables declared in this let block
64 for (const varName of declaredVariables) {
65 const values = variableScope.get(varName);
66 if (values) {
67 values.pop();
68 if (values.length === 0) {
69 variableScope.delete(varName);
70 }
71 }
72 }
73 } else { // "add" or "mult" expression
74 const isAddition = expression[currentIndex] === 'a';
75 currentIndex += isAddition ? 4 : 5; // Skip "add " or "mult "
76
77 // Evaluate first operand
78 const firstOperand = evaluateExpression();
79 currentIndex++; // Skip space between operands
80
81 // Evaluate second operand
82 const secondOperand = evaluateExpression();
83
84 // Perform the operation
85 result = isAddition ? (firstOperand + secondOperand) : (firstOperand * secondOperand);
86 }
87
88 currentIndex++; // Skip closing ')'
89 return result;
90}
91
92// Parse a variable name from current position
93function parseVariable(): string {
94 const startIndex = currentIndex;
95 // Continue until we hit a space or closing parenthesis
96 while (currentIndex < expression.length &&
97 expression[currentIndex] !== ' ' &&
98 expression[currentIndex] !== ')') {
99 currentIndex++;
100 }
101 return expression.substring(startIndex, currentIndex);
102}
103
104// Parse an integer from current position
105function parseInteger(): number {
106 let sign = 1;
107 let value = 0;
108
109 // Handle negative numbers
110 if (expression[currentIndex] === '-') {
111 sign = -1;
112 currentIndex++;
113 }
114
115 // Parse digits
116 while (currentIndex < expression.length &&
117 expression[currentIndex] >= '0' &&
118 expression[currentIndex] <= '9') {
119 value = value * 10 + (expression.charCodeAt(currentIndex) - '0'.charCodeAt(0));
120 currentIndex++;
121 }
122
123 return sign * value;
124}
125
126// Helper function to check if a character is lowercase
127function isLowerCase(char: string): boolean {
128 return char >= 'a' && char <= 'z';
129}
130
Time and Space Complexity
Time Complexity: O(n)
The algorithm performs a single pass through the expression string, where n
is the length of the input expression. Each character is visited at most once during the parsing process:
parseVar()
andparseInt()
advance the indexi
through characters without backtrackingeval()
recursively processes each part of the expression exactly once- For
let
expressions, even though we may have multiple variable assignments, each character in those assignments is still processed only once - The operations for add and mult are constant time
Since we traverse each character at most once and perform constant-time operations (like dictionary lookups and arithmetic operations), the overall time complexity is linear.
Space Complexity: O(n)
The space complexity consists of several components:
- Recursion Stack: In the worst case, we could have deeply nested expressions, leading to a recursion depth of
O(n)
(consider an expression like(add (add (add ...)))
). - Scope Dictionary: The
scope
dictionary uses a defaultdict with lists to store variable values. In the worst case with nestedlet
expressions, we might storeO(n)
total values across all variables, as each character could theoretically be part of a variable name or value. - String Slicing: The
parseVar()
function creates substring slices which could be up toO(n)
in total across all calls.
The dominant factor is the potential recursion depth and the storage for variable scopes, both of which can be proportional to the input size in pathological cases, resulting in O(n)
space complexity.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Scope Management - Not Using Stack for Variables
Pitfall: A common mistake is using a simple dictionary instead of a stack-based approach for variable scope. This fails when the same variable is redefined in nested let expressions.
Problematic Code:
# Wrong approach - using simple dictionary
scope = {} # This won't handle nested scopes correctly
def evaluate_expression():
if expression[index] == "l": # let expression
# ...
old_value = scope.get(var_name) # Try to save old value
scope[var_name] = evaluate_expression() # Overwrite
# ...
if old_value is not None:
scope[var_name] = old_value # Restore - but what if it was undefined?
else:
del scope[var_name] # This gets messy
Why it fails: Consider "(let x 2 (let x 3 x))"
. The inner let should return 3, and after it completes, x should still be 2 in the outer scope. Simple dictionary overwrites lose the outer scope's value.
Solution: Use a stack (list) for each variable:
from collections import defaultdict
scope = defaultdict(list) # Each variable has a stack of values
# When assigning:
scope[var_name].append(value) # Push new value
# When accessing:
return scope[var_name][-1] # Get most recent value
# When leaving scope:
scope[var_name].pop() # Remove the temporary binding
2. Parsing the Final Expression in Let - Ambiguity Problem
Pitfall: Incorrectly determining when we've reached the final expression in a let statement. The final expression could be a variable name, an integer, or another expression.
Problematic Code:
# Wrong - assumes pairs always come in complete sets while index < length and expression[index] != ")": var = parse_variable() index += 1 # skip space value = evaluate_expression() # This might be the final expression! scope[var].append(value)
Why it fails: For "(let x 2 x)"
, after parsing "x" and "2", the next "x" is the final expression to evaluate, not a new variable to assign.
Solution: After parsing a potential variable name, check if the next character is )
or if we're about to parse a value:
var_name = parse_variable() # Check if this is the final expression (no assignment follows) if expression[index] == ")": # This is the final expression - just evaluate the variable result = scope[var_name][-1] break # Otherwise, it's a variable assignment variables_assigned.append(var_name) index += 1 # Skip space scope[var_name].append(evaluate_expression())
3. Global Index Management - Race Conditions in Recursion
Pitfall: Using local index variables or incorrectly managing the global index pointer can cause parsing to get out of sync.
Problematic Code:
def parse_variable(index): # Passing index as parameter
start = index
while index < length and expression[index] not in " )":
index += 1
return expression[start:index], index # Returning new index
# Usage becomes error-prone:
var, index = parse_variable(index) # Easy to forget to update index
Solution: Use nonlocal
to share the index across all parsing functions:
def evaluate(self, expression: str) -> int:
def parse_variable():
nonlocal index # Share the same index variable
start = index
while index < length and expression[index] not in " )":
index += 1 # Automatically updates the shared index
return expression[start:index]
index = 0 # Single shared index
length = len(expression)
4. Not Handling Sequential Variable Dependencies in Let
Pitfall: Evaluating all variable assignments before adding them to scope, which prevents later variables from using earlier ones in the same let expression.
Problematic Code:
# Wrong - evaluate all values first, then assign
values = []
for i in range(0, len(vars), 2):
values.append(evaluate_expression()) # Can't use previous vars!
for i, var in enumerate(vars):
scope[var].append(values[i])
Why it fails: For "(let x 2 y x y)"
, y should be assigned the value of x (which is 2), but if we evaluate all values first, x won't be in scope when evaluating the expression for y.
Solution: Assign variables immediately after evaluating their values:
while True: var_name = parse_variable() # ... check if final expression ... variables_assigned.append(var_name) index += 1 # Immediately add to scope so next variables can use it scope[var_name].append(evaluate_expression())
Which of the following array represent a max heap?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!