LeetCode-Solutions/Python/parse-lisp-expression.py at master · Monika-R/LeetCode-Solutions · GitHub

38 lines (34 loc) · 1.18 KB

# Time: O(n^2)

# Space: O(n^2)

class Solution(object):

def evaluate(self, expression):

"""

:type expression: str

:rtype: int

"""

def getval(lookup, x):

return lookup.get(x, x)

def evaluate(tokens, lookup):

if tokens[0] in ('add', 'mult'):

a, b = map(int, map(lambda x: getval(lookup, x), tokens[1:]))

return str(a+b if tokens[0] == 'add' else a*b)

for i in xrange(1, len(tokens)-1, 2):

if tokens[i+1]:

lookup[tokens[i]] = getval(lookup, tokens[i+1])

return getval(lookup, tokens[-1])

tokens, lookup, stk = [''], {}, []

for c in expression:

if c == '(':

if tokens[0] == 'let':

evaluate(tokens, lookup)

stk.append((tokens, dict(lookup)))

tokens = ['']

elif c == ' ':

tokens.append('')

elif c == ')':

val = evaluate(tokens, lookup)

tokens, lookup = stk.pop()

tokens[-1] += val

else:

tokens[-1] += c

return int(tokens[0])

Expand file tree