Facebook Pixel

736. Parse Lisp Expression

HardStackRecursionHash TableString
Leetcode Link

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:

  1. Integer: A simple integer value (positive or negative)

  2. Variable: A variable name that starts with a lowercase letter followed by zero or more lowercase letters or digits

  3. Let Expression: Has the format "(let v1 e1 v2 e2 ... vn en expr)" where:

    • let is the keyword
    • v1, v2, ..., vn are variable names
    • e1, e2, ..., en are expressions whose values get assigned to the corresponding variables
    • expr 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

  4. Add Expression: Has the format "(add e1 e2)" where:

    • add is the keyword
    • e1 and e2 are expressions to be evaluated
    • The result is the sum of the evaluated values of e1 and e2

  5. Mult Expression: Has the format "(mult e1 e2)" where:

    • mult is the keyword
    • e1 and e2 are expressions to be evaluated
    • The result is the product of the evaluated values of e1 and e2

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 assigned 2
  • Inner let assigns x = 3 and y = 4
  • (add x y) uses the inner scope values: 3 + 4 = 7
  • (mult x 7) uses the outer scope x = 2: 2 * 7 = 14
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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.

Learn more about Stack and Recursion patterns.

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: A defaultdict(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 position
  • n: The length of the expression string

Helper Functions:

  1. 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

  2. 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

  3. 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()
    • Recursive cases (starts with ():
      • Skip the opening parenthesis by incrementing i
      • Check the first character to determine expression type:
      For 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
      • Clean up scope by popping all modified variables: scope[v].pop() for each v in vars
      For add or mult 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

Execution Flow:

  1. Initialize i = 0, n = len(expression), and empty scope
  2. Call eval() which recursively processes the entire expression
  3. The index i automatically advances as we parse, shared across all function calls via nonlocal
  4. Each recursive call to eval() returns an integer value
  5. 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 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example 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 case
  • i = 1 (skip opening parenthesis)
  • expression[1] = 'l' → This is a let expression
  • i = 5 (skip "let ")

Step 2: Parse first variable-value pair

  • Call parseVar() at position 5:
    • j = 5
    • expression[5] = 'x' → valid variable character
    • i = 6
    • expression[6] = ' ' → stop parsing
    • Return "x"
  • var = "x", add to vars = ["x"]
  • i = 7 (skip space)
  • Call eval() to get value for x:
    • expression[7] = '2' → It's an integer
    • Call parseInt(): returns 2
  • 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 case
    • i = 10 (skip opening parenthesis)
    • expression[10] = 'a' → This is an add expression
    • i = 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(): returns 3
  • 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:

  1. The index i advances as we parse, shared across all recursive calls
  2. Variables are pushed onto scope stacks when assigned in let
  3. Variable lookups use the top of the stack (scope[var][-1])
  4. Scope cleanup happens after evaluating the final expression by popping all modified variables
  5. 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() and parseInt() advance the index i through characters without backtracking
  • eval() 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 nested let expressions, we might store O(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 to O(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())
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Stack Intro

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 Review

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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!

Load More