Construct a function that, when given a string containing an expression in infix notation, will return an identical expression in postfix notation.

The operators used will be `+`, `-`, `*`, `/`, and `^` with standard precedence rules and left-associativity of all operators but `^`.

The operands will be single-digit integers between 0 and 9, inclusive.

Parentheses may be included in the input, and are guaranteed to be in correct pairs.

```javascript 
toPostfix("2+7*5"); // Should return "275*+"
toPostfix("3*3/(7+1)"); // Should return "33*71+/"
toPostfix("5+(6-2)*9+3^(7-1)"); // Should return "562-9*+371-^+"
```
```python
to_postfix("2+7*5") # Should return "275*+"
to_postfix("3*3/(7+1)") # Should return "33*71+/"
to_postfix("5+(6-2)*9+3^(7-1)") # Should return "562-9*+371-^+"
```

You may read more about postfix notation, also called Reverse Polish notation, here:
http://en.wikipedia.org/wiki/Reverse_Polish_notation

Difficulty: interview

Starter code:

def to_postfix (infix):
	

Solutions:
def to_postfix (infix):
    prec = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3, '(': 0}
    postfix = []
    stack = []
    for ch in infix:
        if ch in '0123456789':
            postfix.append(ch)
        elif ch in '(':
            stack.append(ch)
        elif ch in ')':
            while stack and stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()
        else:
            while stack and prec[stack[-1]] >= prec[ch]:
                postfix.append(stack.pop())
            stack.append(ch)
            
    while stack:
        postfix.append(stack.pop())
    return ''.join(postfix)

LEFT  = lambda a,b: a>=b
RIGHT = lambda a,b: a>b
PREC  = {'+': 2, '-': 2, '*': 3, '/': 3, '^': 4, '(': 1, ')': 1}

OP_ASSOCIATION = {'+': LEFT, '-': LEFT, '*': LEFT, '/': LEFT, '^': RIGHT}


def to_postfix (infix):
    stack, output = [], []
    for c in infix:
        prec = PREC.get(c)
        
        if prec is None: output.append(c)
        elif c == '(':   stack.append(c)
        elif c == ')':
            while stack and stack[-1] != '(':
                output.append( stack.pop() )
            stack.pop()
        else:
            while stack and OP_ASSOCIATION[c](PREC[stack[-1]], prec):
                output.append( stack.pop() )
            stack.append(c)
            
    return ''.join(output + stack[::-1])

import ast

def to_postfix (infix):
    class PostFixVisitor(ast.NodeVisitor): 
        def visit_BinOp(self, node):
            self.visit(node.left)
            self.visit(node.right)
            self.visit(node.op)

        def visit_Num(self, node):
            postfix.append(str(node.n))
            
        def visit_Add(self, node):
            postfix.append('+')

        def visit_Sub(self, node):
            postfix.append('-')

        def visit_Mult(self, node):
            postfix.append('*')

        def visit_Div(self, node):
            postfix.append('/')

        def visit_Pow(self, node):
            postfix.append('^')

    postfix = []
    p = ast.parse(infix.replace('^', '**'))
    PostFixVisitor().visit(p)
    return ''.join(postfix)


#Infix to Postfix Converter: Implements Dijkstra's Shunting-yard algorithm

#simple stack class to be used by the conversion from infix to postfix
class Stack(object):
    def __init__(self):
        self.stack = []

    def getStack(self):
        return ''.join(self.stack)

    def peek(self):
        try:
            return self.stack[0]
        except IndexError as e:
            raise ValueError(e)
        
    def isEmpty(self):
        return len(self.stack)==0
    
    def pop(self):
        try:
            return self.stack.pop(0)
        except IndexError as e:
            raise ValueError(e)

    def push(self, v):
        self.stack.insert(0, v)
#end stack class



#Implements the Shunting-yard algorithm
class Ifix2PfixConverter():
    __EXP_OP = '^'
    __MUL_OP = '*'
    __DIV_OP = '/'
    __ADD_OP = '+'
    __SUB_OP = '-'
    __L_PAREN = '('
    __R_PAREN = ')'

    __precidenceTable = { __EXP_OP : 4,
                          __MUL_OP : 3, __DIV_OP : 3,
                          __ADD_OP : 2, __SUB_OP : 2 }

    __associativityTable  = { __EXP_OP : 'right',
                              __MUL_OP : 'left', __DIV_OP : 'left',
                              __ADD_OP : 'left', __SUB_OP : 'left' }

    def __init__(self, eqn):
        self.infixEqn = eqn
        self.postfixEqn = []
        self.stack = Stack()
        self.convertToPostfix()

    def isLeftAssociative(self, k):
        return 'left' == self.__associativityTable[k]

    def getPostfixEquation(self):
        return ''.join(self.postfixEqn)

    def isOperator(self, k):
        return  (k in self.__precidenceTable)

    def precidence(self,k):
        return self.__precidenceTable[k]

    def isOperand(self, k):
        return k.isalnum()

    def isLeftParen(self,k):
        return k==self.__L_PAREN

    def isRightParen(self,k):
        return k==self.__R_PAREN


    #Implementation of Dijkstra's Shunting-yard algorithm
    def convertToPostfix(self):

        for c in self.infixEqn:
            if self.isOperand(c):
                self.postfixEqn.append(c)
            elif self.isLeftParen(c):
                self.stack.push(c)
            elif self.isRightParen(c):
                while  not self.stack.isEmpty()  and   not self.isLeftParen(self.stack.peek()): 
                    self.postfixEqn.append(self.stack.pop())
                self.stack.pop() #toss the left parenthesis
            elif self.isOperator(c):
                while not self.stack.isEmpty()  and  self.isOperator(self.stack.peek()) \
                      and ( (self.precidence(self.stack.peek()) > self.precidence(c))  or (self.precidence(self.stack.peek()) == self.precidence(c) and self.isLeftAssociative(c))):
                    self.postfixEqn.append(self.stack.pop())
                self.stack.push(c)
            else:
                raise ValueError('Uknown Character [',c,'] Encountered')

        while not self.stack.isEmpty():
            self.postfixEqn.append(self.stack.pop())
#---end class

def to_postfix (infix):
    converter = Ifix2PfixConverter(infix)
    return converter.getPostfixEquation()
#---end function


operand = set("0123456789")
operator = {'+':1, '-':1, '*':2, '/':2, '^':3}

def to_postfix (infix):
    stack, res = [], []
    for c in "({})".format(infix):
        if c in operand:
            res.append(c)
        elif c == '(':
            stack.append(c)
        elif c == ')':
            while stack[-1] != '(':
                res.append(stack.pop())
            del stack[-1]
        elif c in operator:
            while operator.get(stack[-1], 0) >= operator[c]:
                res.append(stack.pop())
            stack.append(c)
        else:
            raise Exception("Character {} unknown".format(c))
    return ''.join(res)

def to_postfix (infix):
    postfix = ""
    rop = []
    priority = []
    for i, d in enumerate(infix):
        if d in "0123456789":
            postfix += d
        elif d == "(":
            priority.append(len(rop))
        elif d == ")":
            priority.pop()
            postfix += rop.pop()
        else:
            if len(rop) > 0 and (len(priority)==0 or len(rop)>priority[-1]):
                if d in "+-":
                    postfix += "".join(rop[::-1])
                    rop = []
                elif rop[-1] in "*/^":
                    postfix += rop.pop()
            rop.append(d)
    return postfix + "".join(rop[::-1])