We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Parse Lisp Expression

Difficulty: Hard

Problem Description

You are given a string expression representing a Lisp-like expression to return the integer value of. The expression can be an integer, let expression, add expression, mult expression, or an assigned variable, and it follows specific syntactical rules.

Key Insights

  • An expression can be an integer, a variable, or a combination of expressions using "let", "add", or "mult".
  • The "let" expression defines variables and their values, and its value is the result of the final expression.
  • Variable scoping is crucial; the innermost scope is checked first for variable values.
  • Nested expressions can be evaluated sequentially, and variable assignments within a "let" are processed in order.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the expression string. Space Complexity: O(n), for storing variable mappings and recursion stack.

Solution

To solve the problem, we can use a recursive approach combined with a stack to manage the variable scope. We will maintain a dictionary to store variable values and their scopes. The algorithm will parse the expression based on its type (let, add, mult, or integer/variable) and evaluate it accordingly. When we encounter a "let" expression, we will create a new scope for the variables defined within that expression.

Code Solutions

def evaluate(expression: str) -> int:
    def eval_expr(exp, scope):
        if exp[0] != '(':
            if exp.lstrip('-').isdigit():  # it's an integer
                return int(exp)
            return scope[exp]  # return the variable from scope

        tokens = []
        i, n = 1, len(exp)  # skip the opening '('
        while i < n:
            if exp[i] == '(':
                count = 1
                start = i
                while count > 0:
                    i += 1
                    if exp[i] == '(':
                        count += 1
                    elif exp[i] == ')':
                        count -= 1
                tokens.append(exp[start:i + 1])
            else:
                j = i
                while j < n and exp[j] != ' ' and exp[j] != ')':
                    j += 1
                tokens.append(exp[i:j])
                i = j
            i += 1
        
        if tokens[0] == 'let':
            new_scope = scope.copy()
            for j in range(1, len(tokens) - 1, 2):
                new_scope[tokens[j]] = eval_expr(tokens[j + 1], new_scope)
            return eval_expr(tokens[-1], new_scope)
        elif tokens[0] == 'add':
            return eval_expr(tokens[1], scope) + eval_expr(tokens[2], scope)
        elif tokens[0] == 'mult':
            return eval_expr(tokens[1], scope) * eval_expr(tokens[2], scope)

    return eval_expr(expression, {})
← Back to All Questions