736. Parse Lisp Expression

HardStackRecursionHash TableString
Leetcode Link

Problem Description

The problem requires us to interpret and evaluate a given Lisp-like string expression. An expression can be an integer, a variable, or a more complex structure like a let, add, or mult expression. The let expression allows for assigning values to variables and using them in subsequent evaluations within that expression. The add expression represents the sum of two sub-expressions, and the mult expression denotes the product of two sub-expressions.

Expressions are evaluated in the context of their scope, which means that when looking for the value of a variable, the closest scope in terms of parentheses is searched first, and then outward, if needed, until the value is found. It is a given that the expressions provided are legal and do not contain errors.

Here are the key elements of a Lisp-like expression:

  • Integers: These can be both positive or negative numbers.
  • Variables: Strings of lowercase characters and digits, not including reserved keywords.
  • let expression: A series of variable and expression pairs, concluding with an expression for the overall value.
  • add expression: A calculation representing the addition of two expressions.
  • mult expression: A calculation representing the multiplication of two expressions.
  • Scope: The realm in which a variable's value is searched, starting with the innermost set of parentheses.

The challenge lies in properly parsing these expressions, respecting both the syntax and the scopes, and computing the correct integer result.

Intuition

The intuition behind the solution is to recursively parse and evaluate the given expression. The process must manage scopes, particularly when dealing with variables in let expressions. A common approach for such parsing problems is to use a pointer to iterate through the string and break down the problem according to the kind of expression currently being evaluated.

Here's the outline of how we go about it:

  1. Parsing: Identify and break down the components of the expressions. If the expression starts with a number or variable, it gets evaluated to an integer or the value associated with that variable in the current scope. If it's a complex expression like let, add, or mult, it involves additional steps of parsing and evaluation.

  2. Scoping: Maintain a dictionary or stack to hold the variables' values within their respective scopes. When evaluating variables, it's crucial to get the value from the correct scope.

  3. Evaluation: Based on the type of expression (let, add, mult), perform the corresponding evaluation by calling the function recursively.

  4. Iteration and Recursion: Iterate through the expression, advancing the pointer, and whenever a complete sub-expression is encountered, evaluate it recursively.

The provided code leverages nested functions parseVar, parseInt, and eval to accomplish these steps. The eval function is particularly important as it decides which type of expression needs to be evaluated next and calls itself recursively to handle nested expressions.

By approaching the expressions in this manner, each piece is handled in its right context, respecting the rules of scope and operation, ultimately arriving at the final integer result.

Learn more about Stack and Recursion patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The solution provided is a well-structured recursive function that parses and evaluates the Lisp-like expression. The key components of the implementation are the nested helper functions parseVar, parseInt, and the main recursive function eval. Additionally, the data structure used for handling scopes is a dictionary of lists, allowing easy access and modification of variables' values depending on their scope.

Here's a walkthrough of the implementation, step-by-step:

  • Initialization:

    • The pointer i is used to traverse the expression, and n stores the length of the expression for bounds checking.
    • The scope dictionary is initialized using the defaultdict class from collections to handle the scopes of variables efficiently.

  • Helper Functions:

    1. parseVar is a helper function that advances i until a non-variable character (a space or a closing parenthesis) " )" is found and returns the variable name encountered.
    2. parseInt is a similar helper function for parsing integers. It handles potential negatives and accumulates the integer value as it goes along, advancing i.

  • Main Recursive Function (eval):

    • This function checks for the current sub-expression's type. If the current character at i isn't an opening parenthesis, it means we are either dealing with an integer or a variable. If it's a variable (detected by a lowercase letter), the value is fetched from the most recent scope.

    • When a parenthesis is encountered, the function advances i to parse the specific type of expression (let, add, or mult).

    • For a let expression, it alternates between parsing variable names and evaluating their corresponding expressions by recursive calls to eval. The results are stored in the respective scope in scope. After all variable assignments, the let expression's value is evaluated as the value of its last expr.

    • For add and mult expressions, the process involves evaluating the two sub-expressions and then adding or multiplying their values, respectively.

    • Evaluating an Expression:

      • When eval encounters an opening parenthesis, it checks the following characters to determine if it's a let, add, or mult expression. The pointer i is advanced accordingly, jumping over the keywords ("let", "add", "mult").
      • Variables are stored in the scope with their values being marked onto a list, which represents different scopes. The values can be "stacked" on top if the same variable is declared again in a deeper scope, and "popped off" when going out of scope.

    • Scope Management:

      • When the function completes evaluating an expression or variable assignment within a let expression, it removes the variables from the scope by popping them off the stack to clean up and not pollute the outer scopes.

    • Tail Recursion Optimization:

      • Once completed with evaluating the required expressions inside let, add, or mult, it moves past the closing parenthesis and continues with the rest of the expression or returns the final result.

  • Returning Result:

    • After the recursive eval function has completed parsing and evaluating the expression, the result is returned.

This recursive approach with scope management effectively evaluates the given Lisp-like expressions using Python's call stack for naturally handling the nested structure of the expressions and a scope dictionary to simulate the variable environments as defined by Lisp scoping rules.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's consider a simple Lisp-like expression to demonstrate the solution approach:

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

Walkthrough of evaluation:

  1. Initialization:

    • The pointer starts at the beginning of the expression, and the scope is an empty dictionary.

  2. Outer Let Expression:

    • We encounter a let expression and proceed to parse x as the variable and 2 as its value using parseVar and parseInt functions.
    • The variable x is assigned the value 2 in the current scope.

  3. Mult Expression:

    • Next, within the let expression, we find an mult expression.
    • The first part of the mult expression is a variable x, which in the current scope has the value 2.

  4. Inner Let Expression:

    • The second part is an inner let expression (let x 3 y 4 (add x y)).
    • Within this scope, x is reassigned the value 3 and a new variable y is assigned the value 4.
    • Then we encounter an add expression; we evaluate it to get the sum of x and y, which in this inner scope are 3 and 4, thus getting 7 as the result.

  5. Evaluating the mult Expression:

    • Returning to the mult expression, we now have the two sub-expressions evaluated, which are 2 (the value of x in the outer scope) and 7 (the result of the inner let followed by the add expression).
    • We multiply these two values to get 14.

  6. Scope Management:

    • After completing the inner let expression, the variables x and y in that inner scope are removed.

  7. Returning Result:

    • As there are no more expressions to evaluate within the outer let expression, the result of the mult expression (14) is the result of the entire expression.
    • The final result is returned.

This example illustrates how the recursive approach methodically deals with each expression in its right context, respects the scoping rules, and computes the final value.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def evaluate(self, expression: str) -> int:
5        # Helper function to parse variables from the expression.
6        def parse_variable():
7            nonlocal index
8            start = index
9            while index < length and expression[index] not in " )":
10                index += 1
11            return expression[start:index]
12
13        # Helper function to parse integer values from the expression.
14        def parse_integer():
15            nonlocal index
16            sign, value = 1, 0
17            if expression[index] == "-":
18                sign = -1
19                index += 1
20            while index < length and expression[index].isdigit():
21                value = value * 10 + int(expression[index])
22                index += 1
23            return sign * value
24
25        # Main evaluation function to interpret the expression.
26        def evaluate_expression():
27            nonlocal index
28            if expression[index] != "(":
29                # If it's not a sub-expression, return the variable's value or parse the integer.
30                return scope[parse_variable()][-1] if expression[index].islower() else parse_integer()
31          
32            index += 1
33            if expression[index] == "l":
34                # Handling let expression
35                index += 4
36                variables = []
37                while True:
38                    var = parse_variable()
39                    if expression[index] == ")":
40                        result = scope[var][-1]
41                        break
42                    variables.append(var)
43                    index += 1
44                    scope[var].append(evaluate_expression())
45                    index += 1
46                    if not expression[index].islower():
47                        result = evaluate_expression()
48                        break
49                for var in variables:
50                    scope[var].pop()
51            else:
52                # Handling add and multiply expressions
53                is_add = expression[index] == "a"
54                index += 4 if is_add else 5
55                first_operand = evaluate_expression()
56                index += 1
57                second_operand = evaluate_expression()
58                result = first_operand + second_operand if is_add else first_operand * second_operand
59            index += 1
60            return result
61
62        # Initialization of the index and expression length variables 
63        index, length = 0, len(expression)
64        # Dictionary that acts like a stack to keep track of variables' scopes
65        scope = defaultdict(list)
66        # Starting the evaluation process
67        return evaluate_expression()
68
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.HashMap;
5import java.util.List;
6import java.util.Map;
7
8class Solution {
9    private int currentIndex;
10    private String expression;
11    private Map<String, Deque<Integer>> scopes = new HashMap<>();
12
13    public int evaluate(String expression) {
14        this.expression = expression;
15        return evaluateExpression();
16    }
17
18    private int evaluateExpression() {
19        char currentChar = expression.charAt(currentIndex);
20        // If not starting with '(', evaluate variable or integer.
21        if (currentChar != '(') {
22            // If it's a variable, return its last value. Else, parse and return the integer.
23            return Character.isLowerCase(currentChar)
24                ? scopes.get(parseVariable()).peekLast()
25                : parseInteger();
26        }
27        // Skip past the opening parenthesis.
28        currentIndex++;
29        currentChar = expression.charAt(currentIndex);
30        int result = 0;
31
32        // Check if it is a 'let' expression.
33        if (currentChar == 'l') {
34            // Move past "let ".
35            currentIndex += 4;
36            List<String> variables = new ArrayList<>();
37
38            while (true) {
39                String variable = parseVariable();
40              
41                // If we reach the end of the expression, return the last variable's value.
42                if (expression.charAt(currentIndex) == ')') {
43                    result = scopes.get(variable).peekLast();
44                    break;
45                }
46              
47                variables.add(variable);
48                currentIndex++;
49                scopes.computeIfAbsent(variable, k -> new ArrayDeque<>()).offer(evaluateExpression());
50                currentIndex++;
51              
52                // If next character is not a variable, it's an expression to evaluate.
53                if (!Character.isLowerCase(expression.charAt(currentIndex))) {
54                    result = evaluateExpression();
55                    break;
56                }
57            }
58          
59            // Clean up the scope by removing local variable values.
60            for (String v : variables) {
61                scopes.get(v).pollLast();
62            }
63
64        } else {
65            // If it's 'add' or 'mult'.
66            boolean isAddition = currentChar == 'a';
67            // Move past "add " or "mult ".
68            currentIndex += isAddition ? 4 : 5;
69          
70            // Evaluate the first and second expressions.
71            int firstExpression = evaluateExpression();
72            currentIndex++;
73            int secondExpression = evaluateExpression();
74          
75            result = isAddition ? firstExpression + secondExpression : firstExpression * secondExpression;
76        }
77        currentIndex++; // Skip past the closing parenthesis.
78        return result;
79    }
80
81    private String parseVariable() {
82        int startIndex = currentIndex;
83        // Move past variable name.
84        while (currentIndex < expression.length()
85               && expression.charAt(currentIndex) != ' '
86               && expression.charAt(currentIndex) != ')') {
87            currentIndex++;
88        }
89        // Return the variable string.
90        return expression.substring(startIndex, currentIndex);
91    }
92
93    private int parseInteger() {
94        int sign = 1;
95        // Check for and handle a negative sign if present.
96        if (expression.charAt(currentIndex) == '-') {
97            sign = -1;
98            currentIndex++;
99        }
100      
101        int value = 0;
102        // Parse integer by multiplying previous value by 10 and adding the next digit.
103        while (currentIndex < expression.length() && Character.isDigit(expression.charAt(currentIndex))) {
104            value = value * 10 + (expression.charAt(currentIndex) - '0');
105            currentIndex++;
106        }
107
108        // Apply sign and return result.
109        return sign * value;
110    }
111}
112
1#include <string>
2#include <unordered_map>
3#include <vector>
4#include <cctype> // For islower
5
6class Solution {
7public:
8    int index = 0;
9    std::string expression;
10    std::unordered_map<std::string, std::vector<int>> scopes;
11
12    int evaluate(std::string expression) {
13        this->expression = expression;
14        return evaluateExpression();
15    }
16
17    int evaluateExpression() {
18        // If current character is not an opening parenthesis, it must be a variable or an integer
19        if (expression[index] != '(') {
20            return std::islower(expression[index]) ? scopes[parseVariable()].back() : parseInteger();
21        }
22      
23        int ans = 0;
24        ++index; // Skip the '('
25
26        if (expression[index] == 'l') { // If it starts with 'let'
27            index += 4; // Skip the "let"
28            std::vector<std::string> variables;
29            while (true) {
30                std::string variable = parseVariable();
31                if (expression[index] == ')') { // End of let expression
32                    ans = scopes[variable].back();
33                    break;
34                }
35                ++index; // Skip the space or '(' before the expression
36                variables.push_back(variable);
37                scopes[variable].push_back(evaluateExpression());
38                ++index; // Skip the space after expression
39              
40                // If next token is not a variable, it must be an expression 
41                if (!std::islower(expression[index])) {
42                    ans = evaluateExpression();
43                    break;
44                }
45            }
46            // Pop the variables' values from the scope after finishing the "let" expression
47            for (std::string var : variables) {
48                scopes[var].pop_back();
49            }
50        } else { // If it's an "add" or "mult" expression
51            bool isAdd = expression[index] == 'a'; // Check if the operator is add
52            index += isAdd ? 4 : 5; // Skip the "add" or "mult"
53            int firstOperand = evaluateExpression();
54            ++index; // Skip the space between operands
55            int secondOperand = evaluateExpression();
56            ans = isAdd ? firstOperand + secondOperand : firstOperand * secondOperand; // Calculate result
57        }
58        ++index; // Skip the closing parenthesis ')'
59        return ans;
60    }
61
62    // Parses a variable name from the current index
63    std::string parseVariable() {
64        int start = index;
65        while (index < expression.size() && expression[index] != ' ' && expression[index] != ')') ++index;
66        return expression.substr(start, index - start);
67    }
68
69    // Parses an integer (could be negative) from the current index
70    int parseInteger() {
71        int sign = 1, value = 0;
72        if (expression[index] == '-') {
73            sign = -1;
74            ++index; // Skip the negative sign
75        }
76        while (index < expression.size() && std::isdigit(expression[index])) {
77            value = value * 10 + (expression[index] - '0');
78            ++index;
79        }
80        return sign * value;
81    }
82};
83
1import { isLowerCase, isDigit } from 'class-validator';
2
3// Global variable to maintain the current index in the expression
4let index: number = 0;
5// The expression string to evaluate
6let expression: string;
7// A mapping of variable names to their respective scope values
8let scopes: { [variable: string]: number[] } = {};
9
10// Evaluates the given expression string
11function evaluate(exp: string): number {
12    expression = exp;
13    return evaluateExpression();
14}
15
16// Evaluates the current expression
17function evaluateExpression(): number {
18    // If the current character is not an opening parenthesis, it must be a variable or an integer
19    if (expression[index] !== '(') {
20        return isLowerCase(expression[index]) ? scopes[parseVariable()].slice(-1)[0] : parseInteger();
21    }
22  
23    let ans: number = 0;
24    index++; // Skip the '('
25
26    // Handle 'let' expressions
27    if (expression.substring(index, index + 3) === 'let') {
28        index += 4; // Skip the "let"
29        const variables: string[] = [];
30        while (true) {
31            const variable = parseVariable();
32            if (expression[index] === ')') { // End of let expression
33                ans = scopes[variable].slice(-1)[0];
34                break;
35            }
36            index++; // Skip the space or '(' before the expression
37            variables.push(variable);
38            scopes[variable] = (scopes[variable] || []).concat(evaluateExpression());
39            index++; // Skip the space after expression
40          
41            // If next token is not a variable, it must be an expression
42            if (!isLowerCase(expression[index])) {
43                ans = evaluateExpression();
44                break;
45            }
46        }
47        // Pop the variables' values from the scope after 'let' expression
48        variables.forEach(varName => {
49            scopes[varName].pop();
50        });
51    } else { // Handle 'add' or 'mult' expressions
52        const isAdd = expression[index] === 'a'; // Check if the operator is 'add'
53        index += isAdd ? 4 : 5; // Skip the "add" or "mult"
54        const firstOperand = evaluateExpression();
55        index++; // Skip the space between operands
56        const secondOperand = evaluateExpression();
57        // Calculate the result based on the operator
58        ans = isAdd ? firstOperand + secondOperand : firstOperand * secondOperand;
59    }
60    index++; // Skip the closing parenthesis ')'
61    return ans;
62}
63
64// Parses a variable name from the current index
65function parseVariable(): string {
66    const start = index;
67    while (index < expression.length && expression[index] !== ' ' && expression[index] !== ')') index++;
68    return expression.substring(start, index);
69}
70
71// Parses an integer (could be negative) from the current index
72function parseInteger(): number {
73    let sign: number = 1;
74    let value: number = 0;
75    if (expression[index] === '-') {
76        sign = -1;
77        index++; // Skip the negative sign
78    }
79    while (index < expression.length && isDigit(expression[index])) {
80        value = value * 10 + parseInt(expression[index], 10);
81        index++;
82    }
83    return sign * value;
84}
85
Not Sure What to Study? Take the 2-min Quiz：

How many times is a tree node visited in a depth first search?

Time and Space Complexity

The given code implements a parsing and evaluation of a simple expression language that supports integers, variables, and two operations: addition and multiplication, using nested expressions.

Time Complexity:

To determine the time complexity, we need to consider the operations performed by the evaluate function, as well as the helper functions parseVar, parseInt, and eval.

  • The function parseVar runs in O(v) time, where v is the length of the variable name.
  • The function parseInt runs in O(d) time, where d is the number of digits in the number.
  • The recursive function eval is called for each subexpression and each token in the input string. In the worst case, every character can be part of a subexpression (for simple expressions, without nested ones), which would take O(n) time to parse, where n is the length of the whole expression.

Since the eval function invokes parseVar or parseInt for each token, and in the worst-case scenario, each character could be a separate token, the overall time complexity would be O(n) for parsing. However, due to the potential for nested expressions, we have to consider that each subexpression could be recursively evaluated. Considering the nesting, the overall time complexity could be O(n * m), where m is the depth of nesting in the expression.

Under the assumption that the recursion depth is not overly deep, which could be considered O(1) if we assume a limitation on the expression complexity, the overall time would remain O(n) for parsing and evaluating the expression. But, for complete correctness, the time complexity should be considered as O(n * m).

Space Complexity:

Now, let's analyze the space complexity of the code:

  • The scope dictionary may hold a stack for each variable. In the worst case, where each variable is different, this takes O(u) space, where u is the number of unique variables in the expression.
  • Considering the call stack depth, the maximum depth of recursive calls is determined by the depth of the nested expressions, which gives us O(m) space complexity due to recursion.

Therefore, the space complexity is O(u + m) where u is the number of unique variables and m is the maximum depth of the nested expressions.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

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 algomonster s3 us east 2 amazonaws com recursion jpg You first

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫