#!/usr/bin/python
 
"""
From wikipedia: http://en.wikipedia.org/wiki/Reverse_Polish_notation
 
In reverse Polish notation the operators follow their operands; for
instance, to add 3 and 4, one would write '3 4 +' rather than '3 + 4'.
 
If there are multiple operations, the operator is given immediately
after its second operand; so the expression written '3 - 4 + 5' in
conventional notation would be written '3 4 - 5 +' in RPN: first
subtract 4 from 3, then add 5 to that.
 
An advantage of RPN is that it obviates the need for parentheses that
are required by infix. While '3 - 4 * 5' can also be written
'3 - (4 * 5)', that means something quite different from'(3 - 4) * 5'. In
postfix, the former could be written '3 4 5 * -', which unambiguously
means '3 (4 5 *) -' which reduces to '3 20 -'; the latter could be
written '3 4 - 5 *' (or 5 3 4 - *, if you wish to keep similar
formatting), which unambiguously means '(3 4 -) 5 *'.
 
The reverse Polish scheme was proposed in 1954 by Burks, Warren, and
Wright[1] and was independently reinvented by F. L. Bauer and
E. W. Dijkstra in the early 1960s to reduce computer memory access and
utilize the stack to evaluate expressions. The algorithms and notation
for this scheme were extended by Australian philosopher and computer
scientist Charles Hamblin in the mid-1950s.[2][3]
 
During the 1970s and 1980s, RPN was known to many calculator users, as
it was used in some handheld calculators of the time designed for
advanced users: for example, the HP-10C series and Sinclair Scientific
calculators.
 
In computer science, postfix notation is often used in stack-based and
concatenative programming languages.
 
"""
 
from go import *
 
#---| lib stuff |------
 
import sys
def say(x):
  sys.stdout.write(x)
 
#--- interpreter for reverse polish notation
 
def postorder(x):
  return postorder1(x,[])
 
def postorder1(x,out):
  leaf  = lambda y: not isinstance(y,list)
  left  = lambda y: y[0]
  head  = lambda y: y[1]
  right = lambda y: y[2]
  if leaf(x):
    out += [x]
  else:
    postorder1(left(x), out)
    postorder1(right(x),out)
    postorder1(head(x), out)
  return out
 
#@go
def _postorder():
  print postorder( [[1, "+",2],
                    "*",
                    [2, "-", 3]] )
 
#-----------------------------------------
# evaluator for rpn
                     
def rpn(input):
  minus    = lambda x,y : float(x) - float(y)
  plus     = lambda x,y : float(x) + float(y)
  mult     = lambda x,y : float(x) * float(y)
  args     = {"+" : plus, 
              "*" : mult, 
              "-" : minus}
  operator = lambda x: x in args
  stack    = []
  while input:
    token = input.pop(0)
    if not operator(token):
      stack += [token]
    else:
      two = stack.pop()
      one = stack.pop()
      f= args[token]
      stack += [f(one,two)]
  return stack[0]
 
@go
def _shunt():
  say("5 + ((1 + 2) * 4) - 3 = " )
  print rpn([5,1,2,"+",4,"*","+",3,"-"])
 
# -------------------------------------------
# infix to rpn translator
 
# class stuff definitions
 
class Op:
  all = []
  def __init__(i,name,precedence=100):
    i.name=name
    i.precedence = precedence
    Op.all += [i]
  def __repr__(i):
    return i.name + '{' + str(i.precedence) + '}'
 
# parsing utils 
def isa(x):
  "Try to find the operator names 'x'. Else fail."
  for y in Op.all:
    if x == y.name: return y
  return None
    
def isNum(x):
  "Let Python do the heavy lifting"
  try: return int(x)
  except ValueError:
    try: return float(x)
    except ValueError:
      return None
 
# main engine 
import re
class Shunt:
  """ Simple version of Edsger Dijkstra's shunting yard algorithm.
      No associativity, brackets, function symbols, arguments.
      No error checking.
      For full version, see http://goo.gl/pakbVu
  """
  def __init__(i,str):
    say(str + ' : ')
    i.out   = []
    i.stack = []
    for token in i.tokens(str): 
      i.shunt(token)
    # tidy up
    while i.stack: i.up()
  def __repr__(i)   : return str(i.out)
  def over(i,token) : say("o"); i.out   += token
  def down(i,op)    : say("d"); i.stack += [op]
  def up(i)         : say("u"); i.out   += [i.stack.pop()] 
  def somethingIsMoreImportant(i,op):
    return i.stack and op.precedence <= i.stack[-1].precedence
  def tokens(i,str): 
    "dumb tokenizer: assumes tokens one char wide)"
    return list(re.sub("[ \t]*","",str)) 
  def shunt(i,token):
    op = isa(token)
    if not op:
      i.over(token)
    else:
      while i.somethingIsMoreImportant(op):
        i.up()
      i.down(op)
  
# demos
@go
def _shunt():
  Op.all = []
  Op('+',1)
  Op('*',2)
  Op('/',2)
  print Shunt("1 + 2")
  print Shunt("1 + 2 + 3")
  print Shunt("1 + 2 / 3")
  print Shunt("a * b + c / d")
  print Shunt("a * b + c * d")