#---| lib stuff |------

import sys
def say(x):
  sys.stdout.write(x)

#---| class stuff |-----
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.
      For full version, see http://goo.gl/pakbVu"
  """
  def __init__(i,str):
    say(str + ' : ')
    i.out   = []
    i.stack = []
    i.worker(str)
    i.tidy()
  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 worker(i,str): 
    for token in i.tokens(str):
      i.shunt(token) 
  def tidy(i): 
    while i.stack: 
      i.up()
  def shunt(i,token):
    op = isa(token)
    if not op:
      i.over(token)
    else:
      while i.stack and op.precedence <= i.stack[-1].precedence:
        i.up()
      i.down(op)
  def tokens(i,str): 
    "a poor tokenizer: assumes all symbols of length 1"
    def noSpace(str) : 
      return re.sub("[ \t]*","",str)
    return list(noSpace(str))
  
#---| demo stuff |-----
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")

from go import *
eval(todo(__name__,'_shunt'))