# Question 1: 
# We prove this by using proof by contradiction.
# STEP 1) First, we assume that both statement are true:
# a. Preorder traversal ABCDEF 
# b. Inorder DBCFAE 
# Hence, from preorder traversal, we know the root node is A.
# STEP 2) Then, from inorder, we see that there's only E is at A's right. So E must be
# the only right child node of A, and it has no children and no node at its right side.
# STEP 3) However, let's look at preorder again: E is followed by F. This means F is 
# either a child of E, or a node on its right. But, this statement contradicts our previous 
# statement in STEP 2.
# Therefore, our assumption didn't work. Both statement can not be true.



# Question 2a
import operator
def calc(expr):
	# assuming input expression is a string, and each character is separated
	# by a white space. example: '10 2 8 * + 3 -'
	expr = expr.split() # convert expression string into a list
	ops = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}
	i = 0
	while i < len(expr):
		if expr[i] in ops:
			expr[i-2:i+1] = [ops[expr[i]](float(expr[i-2]), float(expr[i-1]))]
			i = i-2
		i += 1
	return expr.pop()
# print (calc('10 2 8 * + 3 -'))
# 23.0
# print (calc(' 1 2 + 3 * 6 + 2 3 + /'))
# 3.0

# Question 2b
# input expression is in Postfix
import BinTree_inProgress
def createTree(expr):
        expr = expr.split()
        stack = []
        ops = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}
        expr.reverse();
        while(expr):
                a = expr.pop()
                if a not in ops:
                        stack.push(a)
                else:
                        op = stack.pop()