736. Parse Lisp Expression - Detailed Explanation

How this works: We use a pointer i that moves through the string. The helper functions parse_var and parse_int read a variable name or integer from the current position. The eval_expr function is the core recursive evaluator:

• If the current position is at a number or variable, it returns the value directly (for variables, looks up the latest value in scope).
• If it encounters a '(', it determines the type by peeking at the substring ("let", "add", or "mult"):

  • For a let-expression, it loops to read assignments. It collects each assigned variable name in vars_assigned. For each assignment, it evaluates the next expression and pushes the value onto that variable’s stack in scope. If it finds a ")" right after a variable name, that means there are no more assignments and that variable name is actually the start of the final expression (as in the case "(let x 2 x)"). The loop breaks when the final expression is evaluated (or when it detects that scenario). After computing the result of the let, it pops the variables in vars_assigned to restore outer values.

  • For add and mult, it simply evaluates the two sub-expressions (operands) recursively and then adds or multiplies them.

• We increment and decrement i appropriately to skip over spaces and parentheses as we parse. By the time eval_expr() returns, i will have advanced past the entire sub-expression it evaluated.

This method evaluates the expression in one pass without re-scanning any portion of the string more than once. It also cleanly handles nested scopes by using the scope stacks to keep track of variable values.

Java Implementation (Optimized)

Explanation: The Java optimized solution uses a class with state: expr (the input string), index (current parse position), and a scope map from variable names to a stack (Deque) of integer values. The evalExpr method closely mirrors the Python version:

• If the current position points to a number or variable (not starting with '('), it returns the value (for variable, scope.get(varName).peek() gives the latest assigned value).

• If it sees (, it checks whether the next part is "let", "add", or "mult" and handles each case:

  • For "let", it reads tokens inside until it finds the final expression. For each assignment, it pushes the new value onto the variable’s stack in scope. It uses scope.computeIfAbsent to ensure a stack exists for a new variable. After finishing the let, it pops the values for all variables that were assigned in this let to restore the outer scope.
  • For "add" and "mult", it evaluates the two operands and computes the result.

• The use of startsWith on the substring helps identify the operation keyword. We carefully move the index to skip processed characters (like the "add" or "let" keywords and the spaces and parentheses).

• The main method demonstrates evaluating an expression; it should print 14 for the given example.

This approach avoids copying the entire environment on each scope entry. Instead, it updates the scope map in place (pushing new values) and then reverts changes by popping. This is more efficient in both time and space.

Complexity Analysis

• Brute Force Approach: Time complexity is roughly O(n²) in the worst case, where n is the length of the expression. This is because we may repeatedly parse parts of the string or copy the environment for nested let scopes. For example, a deeply nested expression with many let assignments could lead to a lot of repeated work. However, for most reasonable inputs (including the examples), it will run in near-linear time relative to the expression size. Space complexity is O(n) due to recursion depth and environment copies. Each recursive call handles a subset of the expression or a new scope.

• Optimized Approach: Average time complexity is O(n), since we make one pass through the string and do constant work (or small overhead) for each character. The parser efficiently handles nested expressions without re-scanning already processed parts. In the worst case, extremely nested or contrived inputs might introduce some overhead (like many nested scopes causing a lot of push/pop operations or repeated checks), but it’s still much more efficient than re-parsing. Space complexity is O(n), primarily from the recursion stack in a deeply nested expression and the space used by the scope stacks. Each variable can have at most as many values on its stack as the nesting depth of scopes, which in worst case is O(n) if each character introduces a new scope (though that’s an unlikely scenario given the syntax).

In summary, the optimized approach is more scalable for larger expressions and ensures we don’t redo work. The brute force approach is simpler to implement but might struggle with very large or deeply nested inputs due to the repeated parsing and copying.

Step-by-Step Walkthrough of an Example

Let’s walk through a complex example to see how the evaluation works step by step. Consider the input:

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

We will evaluate this expression by hand:

1. Outer Expression: (let x 2 (mult x ( ... ))). This is a let expression.

   • We start with an empty environment {}.
   • Assignment 1: x = 2. After this, in the let’s local scope, x is 2. (Outer env: { x: 2 })
   • Now, after assignments, we must evaluate the final expression part: (mult x (let x 3 y 4 (add x y))) with the current environment.

2. Evaluate (mult x (let x 3 y 4 (add x y))): This is a mult expression with two operands:

   • Operand 1: x – a variable. We look up x in the current environment. The innermost assignment for x is 2 (from the outer let). So this operand evaluates to 2.
   • Operand 2: (let x 3 y 4 (add x y)) – another let-expression (nested inside the mult).

3. Inner Let Expression: (let x 3 y 4 (add x y)). We evaluate this inside the context of the outer let:

   • When we enter this inner let, we create a new scope layered on top of the outer scope. At the moment before the inner assignments, x is still 2 (from outer scope) and is remembered.
   • Assignment 1 (inner): x = 3. This shadows the outer x. Now in the inner scope, x is 3 (outer x=2 is still there but hidden underneath).
   • Assignment 2 (inner): y = 4. Now in inner scope, we have x = 3, y = 4.
   • Now evaluate the inner let’s final expression: (add x y) in the context of the inner scope.
     • x in this context is 3 (the inner assignment) and y is 4.
     • So (add x y) = 3 + 4 = 7.
   • The inner let-expression returns 7. Before leaving this let, we pop the inner assignments, restoring any outer values. (So after this, x goes back to 2 as in outer scope, and y is no longer defined in the outer scope.)

4. Back to the mult: Now we have the results of both operands:

   • Operand 1 was 2 (outer x).
   • Operand 2 (the inner let) evaluated to 7.
   • So (mult 2 7) = 14.

5. Outer Let Result: The mult returned 14. Since that was the final expression of the outer let, the outer let-expression evaluates to 14. Any variables defined in the outer let (here x) would be popped if there were an outer scope (in this case, it was the top level, so we’re done).

The final output is 14, which matches the expected result. Throughout this process, note how scoping works:

• Inside the inner (add x y), the value of x was the inner one (3), not the outer one (2).

• After finishing the inner let, the outer x value (2) is still in effect for the remainder of the outer expression.

• Assignments in each let are local and sequential, and once their scope is finished, those assignments don’t exist anymore.

Common Mistakes and How to Avoid Them

• Incorrect Token Splitting: A frequent mistake is to split the expression by spaces naively. This breaks down when expressions are nested. For example, splitting "(mult x (add 1 2))" by spaces yields ["(mult", "x", "(add", "1", "2))"], which is incorrect because "(add 1 2)" is one operand. Always parse taking parentheses into account (e.g., using a stack or pointer to identify whole sub-expressions).

• Not Handling Negative Numbers Properly: Remember that -5 is a single integer token, not two tokens. If you parse character by character, ensure that a '-' followed by digits is recognized as one number token. In our approaches, we handled this in parse_int. Forgetting this could lead to errors or treating - as an operator (which it isn’t in this language).

• Variable Scoping Errors: A common logical error is not restoring the previous value of a variable after leaving a scope. For instance, if a variable x exists in an outer scope and you assign x in a let, you need to revert to the old value when that let finishes. Using a stack for each variable (or copying the environment) helps manage this. If you simply use a global map and don't revert changes, you’ll carry incorrect values into outer scopes.

• Sequential Let Assignments: Misinterpreting the structure of let can cause mistakes. Each vi ei pair should be processed in order. Some might erroneously try to evaluate all ei first before assigning, which would be wrong because later expressions can depend on earlier assigned variables. For example, in (let x 1 x 2 (....)), the second assignment’s expression could refer to x which should still be 1 at that moment. Our evaluation evaluates and assigns one pair at a time, reflecting the sequential nature.

• Missing Base Cases: Not handling simple expressions (like just a number or just a variable by itself) can cause issues. Although the problem input always wraps complex expressions in parentheses, after recursion you will hit cases where you evaluate a substring that's just "5" or "x". Our code checks for expression[0] != '(' to cover this case. Forgetting to do so might lead your code to try to treat a number as an expression and fail.

• Off-by-One Errors in Parsing: When manually moving an index through the string, it’s easy to skip one character too many or too few (for example, not skipping the space after reading an operand, or skipping the closing parenthesis at the wrong time). Careful incrementing of the index and thorough testing on provided examples (and edge cases) can help catch these. In our optimized approach, we incremented i at specific points to consume spaces and parentheses; a mistake there could scramble the parsing.

To avoid these mistakes, it’s helpful to test your solution on the example cases and also on simpler cases:

• Just an integer (e.g., "7") or just a variable with an outer assignment (though standalone variable might not be valid input unless within a let).
• Expressions with negative numbers (e.g., "(add -1 -2)" should yield -3).
• Nested lets that reuse variable names to ensure your scope handling is correct.

Edge Cases to Consider

• Single Number or Variable: The input could be just an integer (e.g., "5") or a variable that was assigned in an outer context. According to the problem, the expression is always legal, so a standalone variable would imply it was assigned in an outer let. But typically, you won’t get an input like "x" alone since there’s no outer context. Nonetheless, ensure your evaluation handles base tokens correctly.

• Negative Values: Ensure that negative integers are parsed as one token and their arithmetic works. Also, variables can hold negative values from calculations, which is fine as long as arithmetic is correct.

• Deep Nesting: The expression could be deeply nested (imagine many layers of let inside each other). Our recursive approach and scope stack should handle this up to the input length limit. In Python, extremely deep recursion could hit recursion limits, but with max length 2000 and the nature of the grammar, it’s unlikely to exceed Python’s recursion limit (which is usually around 1000) significantly. If needed, one could convert recursion to iteration with an explicit stack to avoid that, but it's usually not necessary here.

• Variables with Similar Names: Variables like a and add – the latter is reserved and won’t appear as a variable, but something like a and aa could both exist. Our parsing by spaces and boundaries ensures we get full names, so this should be fine. Just be careful not to confuse a prefix of a variable name as a separate token. For example, if the code looked for keywords by exact match (which we did with startsWith but also checking the context), ensure it doesn’t misidentify a variable named "letdown" as a "let" keyword (in this problem, such a name won't appear because "let" is reserved, but this is a general caution).

• No Extra Spaces: The input has no leading/trailing spaces and single spaces between tokens. If you were to handle arbitrary spacing, you’d need to trim and normalize spaces. The provided input guarantee simplifies parsing (we can reliably use space as a delimiter except when inside nested expression which we handle by counting parentheses).

By considering these edge cases, you can ensure your solution is robust.

Alternative Variations and Related Problems

This problem is essentially about parsing and evaluating expressions with variables and nested scopes. Here are some related problems and variations to practice:

• LeetCode 224: Basic Calculator I – Evaluate a mathematical expression containing +, -, (, ), and integers . This is simpler (no variables or custom operations) but also requires parsing with correct order of operations.

• LeetCode 227: Basic Calculator II – Similar to Basic Calculator I but without parentheses, and adds * and /. Emphasizes parsing and operator precedence.

• LeetCode 772: Basic Calculator III – A follow-up that combines parentheses, +,-,*,/. It’s a bit more complex, involving parsing and possibly using a stack or recursion to handle precedence and parentheses.

• LeetCode 439: Ternary Expression Parser – Parse a string like "T?2:3" (a ternary conditional expression) and evaluate it. It requires parsing a different expression format with ? and : operators and can also be solved with recursion or stack.

• LeetCode 150: Evaluate Reverse Polish Notation – Here the expression is given in Reverse Polish (postfix) form. The parsing is trivial (tokens separated by spaces) but it’s about using a stack to evaluate in the correct order. It’s a different notation but also an expression evaluation problem.

• LeetCode 385: Mini Parser – Parse a nested integer list specified as a string (e.g., "[123,[456,[789]]]"). This involves recursion to handle nested brackets and is conceptually similar to parsing nested parentheses in this problem.