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

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Mathematics

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)


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)

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

	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()
			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())

def to_postfix(infix):
	converter = Ifix2PfixConverter(infix)
	return converter.getPostfixEquation()


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])