Interview Question Expression Compiler

compiler.py

"""Expression Compiler/Evaluator

This is a simple expression compiler.
It has the following limitations
  - supported operation: +,-,/,%,
  - only supports binary operations enclosed in ()
    - ((1+3) + (1+3)) -- valid
    - (1+3) + (1+3) -- invalid
  - does not support implict multiplication 
    - (1(1+3)) -- bad juju
  
"""
__author__ = 'Art Carey'

def evaluate_expression(exp):
  root = exp.pop()
  return evaluate_operator(root,exp)  

def evaluate_operator(op_code,stack):
  op = get_op(op_code)

  #get operands 
  right = stack.pop()
  res2 = right if is_int(right) else evaluate_operator(right,stack) 
  left = stack.pop()
  res1 = left if is_int(left) else evaluate_operator(left,stack) 

  return op(res1,res2)

#hijacked from stackoverflow I know its slow
def is_int(s):
  try:
    int(s)
    return True
  except ValueError:
    return False
  
def get_op(op_code):
  if op_code == '+':
    return lambda x,y: x+y
  elif op_code == '*':
    return lambda x,y: x*y
  elif op_code == '-':
    return lambda x,y: x-y
  elif op_code == '/':
    return lambda x,y: x/y
  elif op_code == '%':
    return lambda x,y: x%y
  
  raise Exception("Invalid OpCode")

def compile_expression(expr):
  return parse_expression(expression[1:-1],[])

def parse_expression(expr,result_stack):

  left = parse_complex(expr) if expr[0] == '(' else expr[0]

  #parse operator
  operator = expr[len(left)]

  #parse right
  right = expr[len(left)+1:]

  if left[0] == '(':
    parse_expression(left[1:-1],result_stack)  
  else:
    result_stack.append(int(left))

  if right[0] == '(':
    parse_expression(right[1:-1],result_stack)  
  else:
    result_stack.append(int(right))

  result_stack.append(operator)

  return result_stack

def parse_complex(string):
  paren_count = 0
  count=0
  for c in string:
    if c == '(':
      paren_count = paren_count+1
    elif c == ')':
      paren_count = paren_count-1
    if paren_count == 0:
      break;
    count = count+1

  return string[0:count+1]

if __name__ == "__main__":
  import getopt
  import sys

  def usage():
    print "Usage:"+sys.argv[0] + " [OPTION]"
    print "Evaluates well formed expressions"
    print "   well formed expression has following properties"
    print "     - binary operation enclosed in parens - (1+3), ((1+3)+(1+3))"
    print "     - no implicit multiplication -> (2(3+3))"
    print "     - no spaces"
    print "     - only uses [+,-,*,/,%] operators"
    print " "
    print "  -e, --expression    provide well formed expression" 
    print "      --help          display help" 
    
  try:
    opts, extraparams = getopt.getopt(sys.argv[1:], "he:",["help","expression="])
    expression = None
    for o,p in opts:
      if o in ['-e', '--expression']:
        expression = p
        stack = compile_expression(expression)
        print evaluate_expression(stack)
      if o in ['--help']:
        usage()  
  except getopt.GetoptError,e:
     usage()