Approach #1: Recursive Parsing [Accepted]

Intuition and Algorithm

This question is relatively straightforward in terms of the idea of the solution, but presents substantial difficulties in the implementation.

Expressions may involve the evaluation of other expressions, which motivates a recursive approach.

One difficulty is managing the correct scope of the variables. We can use a stack of hashmaps. As we enter an inner scope defined by parentheses, we need to add that scope to our stack, and when we exit, we need to pop that scope off.

Our main evaluate function will go through each case of what form the expression could take.

  • If the expression starts with a digit or '-', it's an integer: return it.

  • If the expression starts with a letter, it's a variable. Recall it by checking the current scope in reverse order.

  • Otherwise, group the tokens (variables or expressions) within this expression by counting the "balance" bal of the occurrences of '(' minus the number of occurrences of ')'. When the balance is zero, we have ended a token. For example, (add 1 (add 2 3)) should have tokens '1' and '(add 2 3)'.

  • For add and mult expressions, evaluate each token and return the addition or multiplication of them.

  • For let expressions, evaluate each expression sequentially and assign it to the variable in the current scope, then return the evaluation of the final expression.

Complexity Analysis

  • Time Complexity: , where is the length of expression. Each expression is evaluated once, but within that evaluation we may search the entire scope.

  • Space Complexity: . We may pass new strings to our evaluate function when making intermediate evaluations, each of length . With effort, we could reduce the total space complexity to with interning or passing pointers.

Analysis written by: @awice.