Answer Happy

Overview For this assignment, you are going to a very basic binary tree that can be used to evaluate mathematical expressions. This can be a tad complex. So, please do each of the "parts" in order and test your results as you go. The best way to write any large program in through "incremental design". Start modest, add features, and test as you go. Part 1: Node Class Overview In recursively defined structures, like trees, all the coding (and complexity) is found in the recursive structure itself. In the case of trees, the node will contain the vast amount of the logic and behavior. You are going to create a very, very basic node class. Make sure to come up with a nice, well-documented, and well-written solution. We may build upon it, later, to create more advanced tree structures. Interface Create a very basic node class. All this requires is a left and right link (to another node) and a generic data field. It should also have a few constructors. You need one that will create a node with links to two other nodes. public class Node Node Node String String Double Node (String) Node (String, Node, Node) left right value toString() evaluate () Constructor Constructor that assigns the value, left and right nodes. The value that the node contains. Do not declare it of type "object". This will return the fully parenthesized version of the expression. Do worry about this until Part 4.
2/7 Creating the Infix Expression The following is a binary tree representing a mathematical expression. I've colored the internal nodes brown and the leaves are green (quite appropriate, I must say). Note that all the internal nodes are operators, and all the leaves are operands. The toString() function will return the following: 100% + ((526) + ((202) / 2)) I added color for readability. function toString() returns String if the node is a leaf then result = this.value else & return result end function 5 26 20 To convert the tree to an infix string, we need to construct a string using the sub-strings from the left and right children. Of course, if the node is a leaf, the expression is node itself. Don't worry, it is not hard. 12 2 result = "(" + left.ToString() + this.value with spaces + right.ToString() + ")" end if 2
Part 2: Evaluate Tree Class Overview While all the major logic will be found in the nodes, we need to have a single, centralized class. The purpose of the Evaluate Tree class is to start recursion, store some global attributes (for future versions), and much more. Interface The tree class needs to store the root node. public class EvaluateTree Node String String EvaluateTree () EvaluateTree (Node root) root about () toString() Double evaluate () Constructor. Constructor. Returns text about you - the author of this class. This will return the fully parentheses version of the expression. It calls toString() on the root. Starts recursion from the root node. Do worry about this until Part 4.
Once you have finished your code, you need to test it using some good test data. This tree is the most basic form - which means that creating a test tree will require some long declarations. For example, the following is a Java-like language that creates a basic tree using the Node's constructor: EvaluateTree tree = new EvaluateTree (); tree.root = new Node ("+", new Node ("5"), new Node ("/", new Node ("7"), new Node ("2")); This would result in the following binary tree. 5 7 else 2 So, please make sure your code is working at this point before attempting the evaluate function. The toString() Function would create the following text: Part 4: Evaluation Function Now that you have the basic tree class working - and it is printing correctly - you can work on the Evaluation Function. This function is recursive by nature. The evaluate function must use Post-Order Depth First recursion. This is due to the fact that we need the result from the left and right recursive calls before we can perform a calculation. The pseudocode for evaluate is as follows: return this.value end if End Function (5+ (7/2)) Function Evaluate () returns Double If this.value is an operator> return left. Evaluate right. Evaluate !This will be a huge switch statement You must support the following operators. Don't worry about unary minus or function calls (like Sin and Cos).
Operator * / Addition Subtraction Meaning Multiplication Division Modulus Exponent Part 5: Testing Once you have written the Evaluate Function, it needs to be tested with some valid data. Please make sure to use a valid. You need, at least, 10 tests. Here is a possible output from your program. I'm printing the expression, an arrow, and the result. These are generated using toString() and evaluate(). (5+ (7/2)) --> 8.5 (2.5*(1 + 4)) --> 12.5 ((5 * 26) + ((202) / 2)) --> 139 ((24 / (10 7)) + 34) ...and so on Proper Style 42 Use your own expressions and trees. I don't want to see 30 assignments using the test data above. 5