HardNo. 0736
Parse Lisp Expression — LeetCode 736 Python Solution
- Pattern
- Stack
- Topics
- Stack, Recursion, Hash Table, String
- 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
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
- Time
- O(n)
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 1096 | Brace Expansion II | Hard |
| 2019 | The Score of Students Solving Math Expression | Hard |
| 2434 | Using a Robot to Print the Lexicographically Smallest String | Medium |
| 0745 | Prefix and Suffix Search | Hard |
| 0003 | Longest Substring Without Repeating Characters | Medium |
| 0012 | Integer to Roman | Medium |
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.