Python code to convert algebraic expressions to expression(binary) tree.

Some points to keep in mind:
1. Only -,+,*,/,(,) are supported.
2. Expression supplied is assumed not to contain white spaces.
3. Works only on single digits.
4. Parentheses are assumed to be balanced.
5. There is no error checking.
6. Multiplication and division take precedence over addition and subtraction.

operator_precedence = {
	'(' : 0,
	')' : 0,
	'+' : 1,
	'-' : 1,
	'*' : 2,
	'/' : 2
}

def postfix_convert(infix):
	stack = []
	postfix = [] 
		
	for char in infix:
		if char not in operator_precedence:
			postfix.append(char)
		else:
			if len(stack) == 0:
				stack.append(char)
			else:
				if char == "(":
					stack.append(char)
				elif char == ")":
					while stack[len(stack) - 1] != "(":
						postfix.append(stack.pop())
					stack.pop()
				elif operator_precedence[char] > operator_precedence[stack[len(stack) - 1]]:
					stack.append(char)
				else:
					while len(stack) != 0:
						if stack[len(stack) - 1] == '(':
							break
						postfix.append(stack.pop())
					stack.append(char)
	
	while len(stack) != 0:
		postfix.append(stack.pop())

	return postfix

class Node(object):
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

class ExressionTree(object):
	def __init__(self, root = None):
		self.__root = root 
	
	def inorder(self):
		self.__inorder_helper(self.__root)
		
	def __inorder_helper(self, node):
		if node:
			self.__inorder_helper(node.left)
			print node.value
			self.__inorder_helper(node.right)

	def preorder(self):
		self.__preorder_helper(self.__root)
		
	def __preorder_helper(self, node):
		if node:
			print node.value
			self.__preorder_helper(node.left)
			self.__preorder_helper(node.right)

	def postorder(self):
		self.__postorder_helper(self.__root)
		
	def __postorder_helper(self, node):
		if node:
			self.__postorder_helper(node.left)
			self.__postorder_helper(node.right)
			print node.value

def create_expression_tree(infix):
	postfix = postfix_convert(infix)

	stack = []

	for char in postfix:
		if char not in operator_precedence:
			node = Node(char)	
			stack.append(node)
		else:
			node = Node(char)
			right = stack.pop()
			left = stack.pop()
			node.right = right
			node.left = left
			stack.append(node)
	
	return ExressionTree(stack.pop())

print "In Order:" 
create_expression_tree("(5+3)*6").inorder()
print "Post Order:" 
create_expression_tree("(5+3)*6").postorder()
print "Pre Order:" 
create_expression_tree("(5+3)*6").preorder()
Advertisements