Programming Assignment 2
Due: Tuesday, July 14 at midnight

Collaboration Policy

You may either work alone, or you may work with one other student if you wish. If you choose to work with someone, when turning in your assignment, you must note your partner's name. Make sure the division of labor is equitable and that you both understand the programming involved in the assignment.

Overview

Topic: Binary Expression Tree and Tree Traversal

The files you may need for this assignment are:

• Binary_Tree.h
• BTNode.h
• Expression_Tree.h
• Expression_Tree.cpp
• Test_Expression_Tree.cpp
• Syntax_Error.h
• Makefile
• Test1
• Test2
• Test3
  

Assume that a class Expression_Tree has a data field that is a Binary_Tree. Write an instance function to evaluate an expression stored in a binary tree whose nodes contain either integer values (stored in string objects) or operators (stored in string objects). You function should implement the following algorithm:

Algorithm to Evaluate an Expression Tree:
1. if the root node is an integer
2. Return the integer value.
3. else if the root node is an operator symbol
4. let left_val be the value obtained by recursively applying this algorithm to the left subtree
5. let right_val be the value obtained by recursively applying this algorithm to the right subtree
6. return the value obtained by applying the operator in the root node to the left_val and right_val

Your Task

Your task is to write the functions that get the left subtree and the right subtree of a tree. You must also write the function that determines if a node is a leaf node. In addition, you are to write the functions that do a preorder, inorder, and postorder traversal of a tree.

When you have finished implementing these, you should write a function that evaluates a tree that consists of operators in the internal nodes and integers at the leaf nodes. The function will return the value that the tree evaluates to.

Note that you can do this 2 ways. You can use recursion for this function, or you can traverse the tree and place the entire thing in a list that is in postorder. Then we use a stack and we start traversing the list. If the current node's data is a number, we push it on the stack. Otherwise the data must be an operand. We pop the top two values off the stack, apply the operand, and push the new number back onto the stack and move to the next node in our postorder list. We continue until the postorder list is empty.

Files We Are Providing

In order to do your implementation, you may want to download the following source files:

• Binary_Tree.h
  • In this file, you will need to implement the get_left_subtree, the get_right_subtree, and the is_leaf function. You will also need to implement the preorder, inorder, and postorder traversal of the tree functions.
• BTNode.h
• Expression_Tree.h
• Expression_Tree.cpp
  • In this file, you will need to write the evaluate function, which is a function that reads the data at the current root and, if the data is an operator (+, -, *, /) evaluates the left subtree and the right subtree of the root in order to find integer values on which to apply the operator.
  • Note: you can either do this with recursion or you can do it by storing the postorder traversal of the tree in a list and then using a stack. To use the postorder traversal method, simply start at the beginning of your list created by the postorder traversal. If you encounter a number, push the number onto a stack. If you encounter an operator, pop 2 numbers from the stack and apply the operator to the two numbers (the bottom of the two numbers is the right-hand value, an the top is the left-hand value). The number created by applying the operator to the two popped values should be pushed onto the top of the stack. When this is complete, move to the next value in the postorder traversal list and continue until you reach the end of the postorder traversal list and the stack is empty. You have an error if an operator is encountered in the postorder traversal list and there is one or fewer numbers in the stack. You also have an error if you reach the end of the postorder traversal list and you still have numbers in the stack.
    
• Test_Expression_Tree.cpp
  • This is your main function. In here, you will need to read in a binary expression tree. You will need to print out the tree in the preorder, inorder, and postorder traversal of the tree. You will then need to evaluate the tree and return the tree's value.
• Syntax_Error.h
• Makefile
• Test1
• Test2
• Test3
  

Files to Submit

Programming assignments are due at midnight of the day they are due. You are allowed to submit your assignment via email to the TA, but you must also get a hardcopy of your assignment to the TA by the following day.

Source Code
Please submit all source code files which you have either modified or added. In addition, include a script of the output of the program running the test files.

Readme File
For every assignment, you will be asked to submit such a text file. In general, this provides a way for you to add any further comments you wish to make to the grader.

Testing Your Program

Test your program on the Test files provided.