FilesExpand file tree

master

/

parse-lisp-expression.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

38 lines (34 loc) · 1.18 KB

master

/

parse-lisp-expression.py

Copy path

Top

File metadata and controls

• Code
• Blame

38 lines (34 loc) · 1.18 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

# 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])