736. Parse Lisp Expression
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:
-
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
, ormult
, it involves additional steps of parsing and evaluation. -
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.
-
Evaluation: Based on the type of expression (
let
,add
,mult
), perform the corresponding evaluation by calling the function recursively. -
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.
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, andn
stores the length of the expression for bounds checking. - The
scope
dictionary is initialized using thedefaultdict
class fromcollections
to handle the scopes of variables efficiently.
- The pointer
-
Helper Functions:
parseVar
is a helper function that advancesi
until a non-variable character (a space or a closing parenthesis)" )"
is found and returns the variable name encountered.parseInt
is a similar helper function for parsing integers. It handles potential negatives and accumulates the integer value as it goes along, advancingi
.
-
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
, ormult
). -
For a
let
expression, it alternates between parsing variable names and evaluating their corresponding expressions by recursive calls toeval
. The results are stored in the respective scope inscope
. After all variable assignments, thelet
expression's value is evaluated as the value of its lastexpr
. -
For
add
andmult
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 alet
,add
, ormult
expression. The pointeri
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.
- When
-
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.
- When the function completes evaluating an expression or variable assignment within a
-
Tail Recursion Optimization:
- Once completed with evaluating the required expressions inside
let
,add
, ormult
, it moves past the closing parenthesis and continues with the rest of the expression or returns the final result.
- Once completed with evaluating the required expressions inside
-
-
Returning Result:
- After the recursive
eval
function has completed parsing and evaluating the expression, the result is returned.
- After the recursive
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Initialization:
- The pointer starts at the beginning of the expression, and the scope is an empty dictionary.
-
Outer Let Expression:
- We encounter a
let
expression and proceed to parsex
as the variable and2
as its value usingparseVar
andparseInt
functions. - The variable
x
is assigned the value2
in the current scope.
- We encounter a
-
Mult Expression:
- Next, within the
let
expression, we find anmult
expression. - The first part of the
mult
expression is a variablex
, which in the current scope has the value2
.
- Next, within the
-
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 value3
and a new variabley
is assigned the value4
. - Then we encounter an
add
expression; we evaluate it to get the sum ofx
andy
, which in this inner scope are3
and4
, thus getting7
as the result.
- The second part is an inner
-
Evaluating the
mult
Expression:- Returning to the
mult
expression, we now have the two sub-expressions evaluated, which are2
(the value ofx
in the outer scope) and7
(the result of the innerlet
followed by theadd
expression). - We multiply these two values to get
14
.
- Returning to the
-
Scope Management:
- After completing the inner
let
expression, the variablesx
andy
in that inner scope are removed.
- After completing the inner
-
Returning Result:
- As there are no more expressions to evaluate within the outer
let
expression, the result of themult
expression (14
) is the result of the entire expression. - The final result is returned.
- As there are no more expressions to evaluate within the outer
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
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.
What are the most two important steps in writing a depth first search function? (Select 2)
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 algomonster s3 us east 2 amazonaws com recursion jpg You first
LeetCode 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 we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.