import sys
 
class operator:
    all_ops = {}
    def __init__(self, symbol, precedence, mnemonic):
        self.sym = symbol
        self.prec = precedence
        self.mnem = mnemonic
        if operator.all_ops.has_key(symbol):
            raise SyntaxError, 'Operator already assigned'
        operator.all_ops[symbol] = self        
 
operator('+', 100, 'ADD')
operator('-', 100, 'SUB')
operator('*', 200, 'MUL')
operator('/', 200, 'DIV')
operator('^', 300, 'POW')
 
class bottom_up:
    
    def __init__(self, out_strm):
        self.op_prec = operator.all_ops
        self.out = out_strm
 
        self.lineidx = 0
        self.lblidx = 0
 
    def isnum(self, char):
        if char in '0123456789':
            return 1
        return 0
 
    def isop(self, char):
        if char in self.op_prec.keys():
            return 1
        return 0
 
    def output(self, out):
        self.lineidx += 1
        self.out.write('%04d \t\t %s\n' % (self.lineidx, out))
    
    def evaluate(self, expr):
        
        #print some stats
        print 'Expression : %s' % expr
        print 'Expression Length : %s' % len(expr)
        print ''
 
        #stack for operations
        ops = []
 
        #loops through all 'tokens'
        for char in expr:
 
            #skip whitespace
            if char in '\t ':
                continue
 
            #deal with parenthesised expressions
            elif char is '(':
                ops.append('(')
 
            #when parentheses are closed, pop all operations off the stack
            #until the opening parenthesis is reached, pop it too
            elif char is ')':
                while(1):
                    if not len(ops):
                        raise SyntaxError, 'Parentheses count mismatch'
                    if ops[-1] is '(':
                        ops.pop()
                        break
                    self.output(self.op_prec[ops.pop()].mnem)
 
            #all numbers are immediately output
            if self.isnum(char):
                self.output('PUSH #%s' % char)
 
            #if the current operator has a precedence less than the last
            #operator put on the stack, pop the last operator and output
            #it.  push all operators onto the stack
            elif self.isop(char):
                if len(ops):
                    if not ops[-1] is '(':
                        while(len(ops) and self.op_prec[char].prec <= self.op_prec[ops[-1]].prec):
                            self.output(self.op_prec[ops.pop()].mnem)
                ops.append(char)
 
        #any left over operators on the stack need to be popped to the
        #output
        while(len(ops) <> 0):
            self.output(self.op_prec[ops.pop()].mnem)
 
        #more stats
        print ''
        print 'Lines Output : %s' % self.lineidx
 
import time
 
parser = bottom_up(sys.stdout)
start = time.clock()
#parser.evaluate('3^(6 / 2)*(7-2)')
parser.evaluate('1 + 2 + 3 * 4 * 5 * 6 ^ 2 ^ 1 * 7 * 6 + 8 + 9')
end = time.clock()
print 'Start : %s' % start
print 'End   : %s' % end
print 'Time  : %s' % str(end - start)