Parse Lisp Expression — LeetCode 736 Python Solution
HardStackRecursionHash TableString
- Problem
- #736
- Pattern
- Stack
- Reading time
- 10 min
- Source
- leetcode.com
The 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.
Example
- 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,
Python solution
Python
class Solution:
def evaluate(self, expression: str) -> int:
def parseVar():
nonlocal i
j = i
while i < n and expression[i] not in " )":
i += 1
return expression[j:i]
def parseInt():
nonlocal i
sign, v = 1, 0
if expression[i] == "-":
sign = -1
i += 1
while i < n and expression[i].isdigit():
v = v * 10 + int(expression[i])
i += 1
return sign * v
def eval():
nonlocal i
if expression[i] != "(":
return scope[parseVar()][-1] if expression[i].islower() else parseInt()
i += 1
if expression[i] == "l":
i += 4
vars = []
while 1:
var = parseVar()
if expression[i] == ")":
ans = scope[var][-1]
break
vars.append(var)
i += 1
scope[var].append(eval())
i += 1
if not expression[i].islower():
ans = eval()
break
for v in vars:
scope[v].pop()
else:
add = expression[i] == "a"
i += 4 if add else 5
a = eval()
i += 1
b = eval()
ans = a + b if add else a * b
i += 1
return ans
i, n = 0, len(expression)
scope = defaultdict(list)
return eval()Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 736. Parse Lisp Expression is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
LeetCode 1096Brace Expansion IIHardLeetCode 2019The Score of Students Solving Math ExpressionHardLeetCode 2434Using a Robot to Print the Lexicographically Smallest StringMediumLeetCode 745Prefix and Suffix SearchHardLeetCode 3Longest Substring Without Repeating CharactersMediumLeetCode 12Integer to RomanMedium
Frequently asked questions
- How hard is LeetCode 736. Parse Lisp Expression?
- LeetCode 736. Parse Lisp Expression is rated Hard on LeetCode.
- What is the time complexity of LeetCode 736. Parse Lisp Expression?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 736. Parse Lisp Expression?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 736. Parse Lisp Expression cover?
- LeetCode 736. Parse Lisp Expression is tagged Stack, Recursion, Hash Table and String on LeetCode.