Create an interpreter for the grammar "expression := integer | ( function expression expression )"

addmul.py

# Something I got too nervous doing in an interview

import re

def evalexpr(expr):
  name, operands = expr[0], map(lambda x : int(x), expr[1:])
  if name == 'add':
    return reduce(lambda x, y : x + y, operands, 0)
  elif name == 'mul':
    return reduce(lambda x, y : x * y, operands, 1)

def parse(l):
  m = re.search('\((.*)\)', l)
  s = []

  while m is not None:
    s.append(m.group(1))
    m = re.search('\((.*)\)', m.group(1))

  s.reverse()

  if len(s) < 1:
    return l

  prev = s[0]
  result = evalexpr(prev.strip().split(' '))

  for i in xrange(1, len(s)):
    x = re.sub(r'\(|\)', '', s[i].replace(prev, str(result)))
    result = evalexpr(x.strip().split(' '))
    prev = s[i]

  return result

if __name__ == '__main__':
  expression = '( mul ( add 1 ( add ( mul ( add 1 ( mul ( add 3 4 ) 7 ) ) 2 ) 3 ) ) 5 6 )'
  print parse(expression)
  expression = '( add 2 2 )'
  print parse(expression)