Draw the expression tree for the following fully parenthesized infix expression by building it bottom up:

For this lab, submit a handwritten document for the following two parts:

(a) Draw the expression tree for the following fully parenthesized infix expression by building it bottom up: ( ( ( ( 3 + 1 ) x 3 ) / ( ( 9 5 ) + 2 ) ) - ( ( 3 x ( 7 4 ) ) + 6 ) )

(b) Now, restricting your attention to only the subtree that would correspond to: ( ( ( 3 + 1 ) x 3 ) / ( ( 9 5 ) + 2 ) ) provide the best trace that you can for the execution of the code below. Obviously, animation is needed to most nicely follow the example; a gold star awaits the person that most clearly indicates what is happening for ( ( ( 3 + 1 ) x 3 ) / ( ( 9 5 ) + 2 ) )

The code:

def buildParseTree(fpexp):

fplist = fpexp.split()

pStack = Stack()

eTree = BinaryTree('')

pStack.push(eTree)

currentTree = eTree

for i in fplist:

if i == '(':

currentTree.insertLeft('')

pStack.push(currentTree)

currentTree = currentTree.getLeftChild()

elif i not in ['+', '-', '*', '/', ')']:

currentTree.setRootVal(int(i))

parent = pStack.pop()

currentTree = parent

elif i in ['+', '-', '*', '/']:

currentTree.setRootVal(i)

currentTree.insertRight('')

pStack.push(currentTree)

currentTree = currentTree.getRightChild()

elif i == ')':

currentTree = pStack.pop()

else:

raise ValueError

return eTree