Problem

You are given a string expression representing a Lisp-like expression to return the integer value of.

The syntax for these expressions is given as follows.

  • An expression is either an integer, let expression, add expression, mult expression, or an assigned variable. Expressions always evaluate to a single integer.
  • (An integer could be positive or negative.)
  • A let expression takes the form "(let v1 e1 v2 e2 ... vn en expr)", where let is always the string "let", then there are one or more pairs of alternating variables and expressions, meaning that the first variable v1 is assigned the value of the expression e1, the second variable v2 is assigned the value of the expression e2, and so on sequentially; and then the value of this let expression is the value of the expression expr.
  • An add expression takes the form "(add e1 e2)" where add is always the string "add", there are always two expressions e1, e2 and the result is the addition of the evaluation of e1 and the evaluation of e2.
  • A mult expression takes the form "(mult e1 e2)" where mult is always the string "mult", there are always two expressions e1, e2 and the result is the multiplication of the evaluation of e1 and the evaluation of e2.
  • For this question, we will use a smaller subset of variable names. A variable starts with a lowercase letter, then zero or more lowercase letters or digits. Additionally, for your convenience, the names "add", "let", and "mult" are protected and will never be used as variable names.
  • Finally, there is the concept of scope. When an expression of a variable name is evaluated, within the context of that evaluation, the innermost scope (in terms of parentheses) is checked first for the value of that variable, and then outer scopes are checked sequentially. It is guaranteed that every expression is legal. Please see the examples for more details on the scope.

Examples

Example 1

1
2
3
4
5

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14
Explanation: In the expression (add x y), when checking for the value of the variable x,
we check from the innermost scope to the outermost in the context of the variable we are trying to evaluate.
Since x = 3 is found first, the value of x is 3.

Example 2

1
2
3

Input: expression = "(let x 3 x 2 x)"
Output: 2
Explanation: Assignment in let statements is processed sequentially.

Example 3

1
2
3
4

Input: expression = "(let x 1 y 2 x (add x y) (add x y))"
Output: 5
Explanation: The first (add x y) evaluates as 3, and is assigned to x.
The second (add x y) evaluates as 3+2 = 5.

Constraints

  • 1 <= expression.length <= 2000
  • There are no leading or trailing spaces in expression.
  • All tokens are separated by a single space in expression.
  • The answer and all intermediate calculations of that answer are guaranteed to fit in a 32-bit integer.
  • The expression is guaranteed to be legal and evaluate to an integer.

Solution

Method 1 – Recursive Parsing with Scope Stack

Intuition

Lisp expressions are deeply nested and variables can be shadowed in inner scopes. To evaluate them, we need to parse the string recursively, maintaining a stack of variable scopes so that variable lookups always use the innermost definition. This approach allows us to handle let, add, and mult expressions, as well as variable assignments and lookups, in a way that respects the scoping rules described in the problem.

Approach

  1. Use a recursive function to parse and evaluate the expression.
  2. Maintain a stack of dictionaries to represent variable scopes. Push a new scope for each let expression.
  3. For let expressions, sequentially assign variables in the current scope, then evaluate the final expression.
  4. For add and mult, recursively evaluate both arguments and apply the operation.
  5. For variables, look up their value from the innermost scope outward.
  6. For integers, return their value directly.
  7. Carefully handle tokenization to split the expression into meaningful parts.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
    int evaluate(string expression) {
        int pos = 0;
        return eval(expression, pos, vector<unordered_map<string, int>>());
    }
private:
    int eval(const string& expr, int& pos, vector<unordered_map<string, int>> scopes) {
        if (expr[pos] != '(') {
            if (isdigit(expr[pos]) || expr[pos] == '-') {
                int start = pos;
                while (pos < expr.size() && (isdigit(expr[pos]) || expr[pos] == '-')) pos++;
                return stoi(expr.substr(start, pos - start));
            } else {
                int start = pos;
                while (pos < expr.size() && expr[pos] != ' ' && expr[pos] != ')') pos++;
                string var = expr.substr(start, pos - start);
                for (int i = scopes.size() - 1; i >= 0; --i) {
                    if (scopes[i].count(var)) return scopes[i][var];
                }
                return 0;
            }
        }
        pos++; // skip '('
        int start = pos;
        while (expr[pos] != ' ' && expr[pos] != ')') pos++;
        string type = expr.substr(start, pos - start);
        if (type == "let") {
            scopes.push_back({});
            pos++;
            while (true) {
                if (expr[pos] == '(' || isdigit(expr[pos]) || expr[pos] == '-' || isalpha(expr[pos])) {
                    int val = eval(expr, pos, scopes);
                    scopes.pop_back();
                    while (pos < expr.size() && expr[pos] == ' ') pos++;
                    return val;
                }
                int var_start = pos;
                while (expr[pos] != ' ') pos++;
                string var = expr.substr(var_start, pos - var_start);
                pos++;
                int val = eval(expr, pos, scopes);
                scopes.back()[var] = val;
                while (pos < expr.size() && expr[pos] == ' ') pos++;
            }
        } else if (type == "add" || type == "mult") {
            pos++;
            int a = eval(expr, pos, scopes);
            pos++;
            int b = eval(expr, pos, scopes);
            pos++;
            return type == "add" ? a + b : a * b;
        }
        return 0;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

package main
import (
    "strconv"
    "strings"
)
func evaluate(expression string) int {
    var eval func(expr string, scopes []map[string]int) int
    eval = func(expr string, scopes []map[string]int) int {
        expr = strings.TrimSpace(expr)
        if expr[0] != '(' {
            if n, err := strconv.Atoi(expr); err == nil {
                return n
            }
            for i := len(scopes) - 1; i >= 0; i-- {
                if v, ok := scopes[i][expr]; ok {
                    return v
                }
            }
            return 0
        }
        expr = expr[1 : len(expr)-1]
        tokens := tokenize(expr)
        if tokens[0] == "let" {
            scopes = append(scopes, map[string]int{})
            i := 1
            for i+1 < len(tokens) {
                scopes[len(scopes)-1][tokens[i]] = eval(tokens[i+1], scopes)
                i += 2
            }
            val := eval(tokens[i], scopes)
            scopes = scopes[:len(scopes)-1]
            return val
        } else if tokens[0] == "add" {
            return eval(tokens[1], scopes) + eval(tokens[2], scopes)
        } else if tokens[0] == "mult" {
            return eval(tokens[1], scopes) * eval(tokens[2], scopes)
        }
        return 0
    }
    return eval(expression, []map[string]int{})
}
func tokenize(expr string) []string {
    var tokens []string
    bal := 0
    start := 0
    for i := 0; i < len(expr); i++ {
        if expr[i] == ' ' && bal == 0 {
            tokens = append(tokens, expr[start:i])
            start = i + 1
        } else if expr[i] == '(' {
            bal++
        } else if expr[i] == ')' {
            bal--
        }
    }
    tokens = append(tokens, expr[start:])
    return tokens
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import java.util.*;
class Solution {
    public int evaluate(String expression) {
        return eval(expression, new ArrayList<>());
    }
    private int eval(String expr, List<Map<String, Integer>> scopes) {
        expr = expr.trim();
        if (expr.charAt(0) != '(') {
            try {
                return Integer.parseInt(expr);
            } catch (NumberFormatException e) {
                for (int i = scopes.size() - 1; i >= 0; i--) {
                    if (scopes.get(i).containsKey(expr)) {
                        return scopes.get(i).get(expr);
                    }
                }
                return 0;
            }
        }
        expr = expr.substring(1, expr.length() - 1);
        List<String> tokens = tokenize(expr);
        if (tokens.get(0).equals("let")) {
            scopes.add(new HashMap<>());
            int i = 1;
            while (i + 1 < tokens.size()) {
                scopes.get(scopes.size() - 1).put(tokens.get(i), eval(tokens.get(i + 1), scopes));
                i += 2;
            }
            int val = eval(tokens.get(i), scopes);
            scopes.remove(scopes.size() - 1);
            return val;
        } else if (tokens.get(0).equals("add")) {
            return eval(tokens.get(1), scopes) + eval(tokens.get(2), scopes);
        } else if (tokens.get(0).equals("mult")) {
            return eval(tokens.get(1), scopes) * eval(tokens.get(2), scopes);
        }
        return 0;
    }
    private List<String> tokenize(String expr) {
        List<String> tokens = new ArrayList<>();
        int bal = 0, start = 0;
        for (int i = 0; i < expr.length(); i++) {
            if (expr.charAt(i) == ' ' && bal == 0) {
                tokens.add(expr.substring(start, i));
                start = i + 1;
            } else if (expr.charAt(i) == '(') {
                bal++;
            } else if (expr.charAt(i) == ')') {
                bal--;
            }
        }
        tokens.add(expr.substring(start));
        return tokens;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    fun evaluate(expression: String): Int {
        return eval(expression, mutableListOf())
    }
    private fun eval(expr: String, scopes: MutableList<MutableMap<String, Int>>): Int {
        val e = expr.trim()
        if (e[0] != '(') {
            return e.toIntOrNull() ?: scopes.reversed().firstOrNull { it.containsKey(e) }?.get(e) ?: 0
        }
        val inner = e.substring(1, e.length - 1)
        val tokens = tokenize(inner)
        if (tokens[0] == "let") {
            scopes.add(mutableMapOf())
            var i = 1
            while (i + 1 < tokens.size) {
                scopes.last()[tokens[i]] = eval(tokens[i + 1], scopes)
                i += 2
            }
            val v = eval(tokens[i], scopes)
            scopes.removeAt(scopes.size - 1)
            return v
        } else if (tokens[0] == "add") {
            return eval(tokens[1], scopes) + eval(tokens[2], scopes)
        } else if (tokens[0] == "mult") {
            return eval(tokens[1], scopes) * eval(tokens[2], scopes)
        }
        return 0
    }
    private fun tokenize(expr: String): List<String> {
        val tokens = mutableListOf<String>()
        var bal = 0
        var start = 0
        for (i in expr.indices) {
            if (expr[i] == ' ' && bal == 0) {
                tokens.add(expr.substring(start, i))
                start = i + 1
            } else if (expr[i] == '(') {
                bal++
            } else if (expr[i] == ')') {
                bal--
            }
        }
        tokens.add(expr.substring(start))
        return tokens
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def evaluate(self, expression: str) -> int:
        def eval_expr(expr: str, scopes: list[dict[str, int]]) -> int:
            expr = expr.strip()
            if expr[0] != '(':  # integer or variable
                try:
                    return int(expr)
                except ValueError:
                    for scope in reversed(scopes):
                        if expr in scope:
                            return scope[expr]
                    return 0
            expr = expr[1:-1]
            tokens = tokenize(expr)
            if tokens[0] == 'let':
                scopes.append({})
                i = 1
                while i + 1 < len(tokens):
                    scopes[-1][tokens[i]] = eval_expr(tokens[i + 1], scopes)
                    i += 2
                val = eval_expr(tokens[i], scopes)
                scopes.pop()
                return val
            elif tokens[0] == 'add':
                return eval_expr(tokens[1], scopes) + eval_expr(tokens[2], scopes)
            elif tokens[0] == 'mult':
                return eval_expr(tokens[1], scopes) * eval_expr(tokens[2], scopes)
            return 0
        def tokenize(expr: str) -> list[str]:
            tokens = []
            bal = 0
            start = 0
            for i, c in enumerate(expr):
                if c == ' ' and bal == 0:
                    tokens.append(expr[start:i])
                    start = i + 1
                elif c == '(': bal += 1
                elif c == ')': bal -= 1
            tokens.append(expr[start:])
            return tokens
        return eval_expr(expression, [])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

impl Solution {
    pub fn evaluate(expression: String) -> i32 {
        fn eval(expr: &str, scopes: &mut Vec<std::collections::HashMap<String, i32>>) -> i32 {
            let expr = expr.trim();
            if !expr.starts_with('(') {
                if let Ok(n) = expr.parse::<i32>() {
                    return n;
                }
                for scope in scopes.iter().rev() {
                    if let Some(&v) = scope.get(expr) {
                        return v;
                    }
                }
                return 0;
            }
            let inner = &expr[1..expr.len()-1];
            let tokens = tokenize(inner);
            if tokens[0] == "let" {
                scopes.push(std::collections::HashMap::new());
                let mut i = 1;
                while i + 1 < tokens.len() {
                    let val = eval(&tokens[i+1], scopes);
                    scopes.last_mut().unwrap().insert(tokens[i].to_string(), val);
                    i += 2;
                }
                let v = eval(&tokens[i], scopes);
                scopes.pop();
                return v;
            } else if tokens[0] == "add" {
                return eval(&tokens[1], scopes) + eval(&tokens[2], scopes);
            } else if tokens[0] == "mult" {
                return eval(&tokens[1], scopes) * eval(&tokens[2], scopes);
            }
            0
        }
        fn tokenize(expr: &str) -> Vec<String> {
            let mut tokens = vec![];
            let mut bal = 0;
            let mut start = 0;
            let chars: Vec<char> = expr.chars().collect();
            for i in 0..chars.len() {
                if chars[i] == ' ' && bal == 0 {
                    tokens.push(expr[start..i].to_string());
                    start = i + 1;
                } else if chars[i] == '(' {
                    bal += 1;
                } else if chars[i] == ')' {
                    bal -= 1;
                }
            }
            tokens.push(expr[start..].to_string());
            tokens
        }
        eval(&expression, &mut vec![])
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    evaluate(expression: string): number {
        function evalExpr(expr: string, scopes: Array<Record<string, number>>): number {
            expr = expr.trim();
            if (expr[0] !== '(') {
                const n = Number(expr);
                if (!isNaN(n)) return n;
                for (let i = scopes.length - 1; i >= 0; i--) {
                    if (scopes[i][expr] !== undefined) return scopes[i][expr];
                }
                return 0;
            }
            expr = expr.slice(1, -1);
            const tokens = tokenize(expr);
            if (tokens[0] === 'let') {
                scopes.push({});
                let i = 1;
                while (i + 1 < tokens.length) {
                    scopes[scopes.length - 1][tokens[i]] = evalExpr(tokens[i + 1], scopes);
                    i += 2;
                }
                const val = evalExpr(tokens[i], scopes);
                scopes.pop();
                return val;
            } else if (tokens[0] === 'add') {
                return evalExpr(tokens[1], scopes) + evalExpr(tokens[2], scopes);
            } else if (tokens[0] === 'mult') {
                return evalExpr(tokens[1], scopes) * evalExpr(tokens[2], scopes);
            }
            return 0;
        }
        function tokenize(expr: string): string[] {
            const tokens: string[] = [];
            let bal = 0, start = 0;
            for (let i = 0; i < expr.length; i++) {
                if (expr[i] === ' ' && bal === 0) {
                    tokens.push(expr.slice(start, i));
                    start = i + 1;
                } else if (expr[i] === '(') {
                    bal++;
                } else if (expr[i] === ')') {
                    bal--;
                }
            }
            tokens.push(expr.slice(start));
            return tokens;
        }
        return evalExpr(expression, []);
    }
}

Complexity

  • ⏰ Time complexity: O(N) – Each character is parsed once, but recursion and tokenization may add overhead for deeply nested expressions.
  • 🧺 Space complexity: O(D) – D is the maximum depth of nested scopes (let expressions), due to recursion and scope stack.