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('=', 50 , 'POP')
operator('+', 100, 'ADD')
operator('-', 100, 'SUB')
operator('*', 200, 'MUL')
operator('/', 200, 'DIV')
operator('^', 300, 'POW')
operator('@', 50 , 'END')

eq = 0
ay = 1
by = 2

precedence_table =  [
#                       +   -   *   /   ^   (   )   @
                    [   by, by, ay, ay, ay, ay, by, by ],   # +
                    [   by, by, ay, ay, ay, ay, by, by ],   # -
                    [   by, by, by, by, by, ay, by, by ],   # *
                    [   by, by, by, by, by, ay, by, by ],   # /
                    [   by, by, by, by, by, ay, by, by ],   # ^
                    [   ay, ay, ay, ay, ay, ay, eq, by ],   # (
                    [   by, by, by, by, by, eq, by, by ],   # )
                    [   ay, ay, ay, ay, ay, ay, ay, eq ],   # @
                    ]

def get_precedence(a, b):
    mapping = {'+': 0, '-': 1, '*': 2, '/': 3, '^': 4, '{': 5, ')': 6, '@': 7 }
    return precedence_table[mapping[a]][mapping[b]]

class lex:
    '''Class to hold lexer related variables'''

    digits = '0123456789'
    alpha = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    ident = alpha + digits + '_'
    ops = '+-*/^'
    newline = ';'

    addsub = ['+', '-']
    muldiv = ['*', '/']
    boolops = ['<', '>', '==', '!=']

    unknown = 0
    number = 1
    ident = 2
    operator = 3

    def __init__(self, code):
        self.pos = 0
        self.char = code[0]
        self.code = code
        self.count = len(code)
        self.col = 1
        self.sym = None
        self.symtype = None
        self.linebuf = ''
        self.line = 1
        self.end = False
        self.next_symbol()

    def isdigit(self):
        if self.char in lex.digits:
            return True
        return False

    def isnumber(self):
        if sum([1 for i in self.sym if i in lex.digits]) < len(self.sym):
            return False
        return True

    def isalpha(self):
        if self.char in lex.alpha:
            return True
        return False

    def isident(self):
        if self.char in lex.ident:
            return True
        return False

    def isidentifier(self):
        if self.sym[0] in lex.alpha and sum([1 for i in self.sym[1:] if i in lex.ident]) == len(self.sym) - 1:
            return True
        return False

    def isop(self):
        if self.char in lex.ops:
            return True
        return False

    def next_char(self):
        #print self.char
        char = self.char
        self.pos += 1
        self.col += 1
        if self.pos >= self.count:
            self.end = True
            return
        self.char = self.code[self.pos]
        self.linebuf += self.char

    def next_symbol(self):
        while(1):
            if self.end:
                self.sym = 'END'
                return
            if self.char in '''	
 ''':
                self.next_char()
                continue
            elif self.char is lex.newline:
                self.line += 1
                self.col = 1
                self.linebuf = ''
                self.next_char()           #for when there is more than 1 line
            elif self.isdigit():
                num = ''
                while(1):
                    num += self.char
                    self.next_char()
                    if not self.isdigit():
                        self.sym = num
                        self.symtype = lex.number
                        return
            elif self.isalpha():
                ident = ''
                while(1):
                    ident += self.char
                    self.next_char()
                    if not self.isident():
                        self.sym = ident
                        self.symtype = lex.ident
                        return
            elif self.isop():
                op = ''
                while(1):
                    op += self.char
                    self.next_char()
                    if not self.isop():
                        self.sym = op
                        self.symtype = lex.operator
                        return
            else:
                self.sym = self.char
                self.symtype = lex.unknown
                self.next_char()
                return

class bottom_up:
    
    def __init__(self, out_strm, lexer):
        self.op_prec = operator.all_ops
        self.out = out_strm
        self.lexer = lexer
        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 		 %s
''' % (self.lineidx, out))
    
    def evaluate(self):
        
        #print some stats
        print 'Expression : %s' % self.lexer.code
        print 'Expression Length : %s' % len(self.lexer.code)
        print ''

        #stack for operations
        ops = ['@']

        #loops through all 'tokens'
        while(self.lexer.sym <> 'END'):

            sym = self.lexer.sym
            stype = self.lexer.symtype

            #all numbers are immediately output
            if stype == lex.number:
                self.output('PUSH #%s' % sym)

            #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 stype == lex.operator:
                prec = get_precedence(ops[-1], sym)
                if prec == ay or prec == eq:
                    ops.append(sym)
                else:
                    while(get_precedence(ops[-1], sym) == by):
                        self.output(operator.all_ops[ops.pop()].mnem)
                    ops.append(sym)

            self.lexer.next_symbol()

        #any left over operators on the stack need to be popped to the
        #output
        #print ops
        while(len(ops) <> 0):
            self.output(self.op_prec[ops.pop()].mnem)

        #more stats
        print ''
        print 'Lines Output : %s' % self.lineidx

import time

lexer = lex('3*4*6*5;')
parser = bottom_up(sys.stdout, lexer)
start = time.clock()
parser.evaluate()
end = time.clock()
print 'Start : %s' % start
print 'End   : %s' % end
print 'Time  : %s' % str(end - start)