# returns (value, remaining_expr)
def getterm(expr, incoming_rank=0):
  #print "expr: %s rank: %d" %(expr, incoming_rank)
  if expr=="":
    raise Exception("expecting term, instead end of string")
  c=expr[0]
  if c == '-' or c == '+':  # unary
    (val, remains) = getterm(expr[1:], incoming_rank=2)
    if c == '-':
      val = -val
  elif c >= '0' and c <= '9':
    (val, remains) = (int(c) - int('0'), expr[1:])
    while len(remains) > 0 and remains[0] >= '0' and remains[0] <= '9':
      val = val*10 + int(remains[0]) - int('0')
      remains = remains[1:]
  elif c == '(':
    (val, remains) = getterm(expr[1:], incoming_rank=0)
    if remains[0] != ')':
      raise Exception('unclosed paren')
    remains = remains[1:]
  else:
    raise Exception('expecting term, instead got ' + expr)

  while len(remains) > 0:
    op = remains[0]
    if op == ')':
      return (val, remains)
    if op == '-' or op == '+':
      if incoming_rank >= 1:
        break
      (val2, remains) = getterm(remains[1:], incoming_rank=1)
      if op == '-':
        val = val - val2
      else:
        val = val + val2
    elif op == '*' or op == '/':
      if incoming_rank >= 2:
        break
      (val2, remains) = getterm(remains[1:], incoming_rank=2)
      if op == '/':
        val = val / val2
      else:
        val = val * val2
    elif op == '^':
      if incoming_rank >= 3:
        break
      (val2, remains) = getterm(remains[1:], incoming_rank=3)
      val = val ** val2
    else:
      raise Exception('unrecognized two-place op at: ' + remains)
  return (val, remains)

def evalexpr(expr):
  (val, remains) = getterm(expr)
  if len(remains) > 0:
    raise Exception('junk at end: ' + remains)
  print "%s = %d" %(expr, val)

evalexpr("2+2")
evalexpr("(2)")
evalexpr("22+3")
evalexpr("2+3*5")
evalexpr("(2+3)*5")
evalexpr("((2+3)^2*2)+3*5")
evalexpr("-3")
evalexpr("-10^2")