LeetCode 736: Parse Lisp Expression Solution

Master LeetCode problem 736 (Parse Lisp Expression), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

736. Parse Lisp Expression

Hard

Hash Table String Stack Recursion

Problem Explanation

Explanation:

We can solve this problem using a stack to keep track of the scopes and a map to store the variable values.
We iterate through the expression character by character, handling different types of expressions accordingly.
For each let expression, we recursively evaluate the sub-expressions and update the variable values.
For add and mult expressions, we evaluate the sub-expressions and perform addition or multiplication.
Finally, we return the value of the final expression.

Time Complexity: O(n) Space Complexity: O(n)

Solution Code

class Solution {
    public int evaluate(String expression) {
        return evaluateExpression(expression, new HashMap<>());
    }
    
    private int evaluateExpression(String expression, Map<String, Integer> variables) {
        if (expression.charAt(0) != '(') {
            if (Character.isDigit(expression.charAt(0)) || expression.charAt(0) == '-') {
                return Integer.parseInt(expression);
            }
            return variables.get(expression);
        }
        
        Map<String, Integer> newVariables = new HashMap<>(variables);
        List<String> tokens = parseExpression(expression.substring(expression.charAt(1) == 'l' ? 5 : 1, expression.length() - 1));
        if (expression.startsWith("(add")) {
            return evaluateExpression(tokens.get(0), newVariables) + evaluateExpression(tokens.get(1), newVariables);
        } else if (expression.startsWith("(mult")) {
            return evaluateExpression(tokens.get(0), newVariables) * evaluateExpression(tokens.get(1), newVariables);
        } else {
            for (int i = 0; i < tokens.size() - 2; i += 2) {
                newVariables.put(tokens.get(i), evaluateExpression(tokens.get(i + 1), newVariables));
            }
            return evaluateExpression(tokens.get(tokens.size() - 1), newVariables);
        }
    }
    
    private List<String> parseExpression(String expression) {
        List<String> tokens = new ArrayList<>();
        int balance = 0;
        StringBuilder sb = new StringBuilder();
        for (String token : expression.split(" ")) {
            for (char c : token.toCharArray()) {
                if (c == '(') balance++;
                if (c == ')') balance--;
            }
            if (sb.length() > 0) {
                sb.append(" ");
            }
            sb.append(token);
            if (balance == 0) {
                tokens.add(sb.toString());
                sb.setLength(0);
            }
        }
        return tokens;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 736 (Parse Lisp Expression)?

This page provides optimized solutions for LeetCode problem 736 (Parse Lisp Expression) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 736 (Parse Lisp Expression)?

The time complexity for LeetCode 736 (Parse Lisp Expression) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 736 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 736 in Java, C++, or Python.

Back to LeetCode Solutions