# JJC Algebraic Expression in P

Assignment 1 An algebraic expression tree Goals: • Review and develop a deep and comprehensive understanding of the object-oriented paradigm • Review data structures such as lists, stacks, trees, etc. • Review programming techniques such as recursion A binary tree is a tree in which no node can have more than two children. An algebraic expression can be represented in a binary tree, an expression tree. The leaves of an expression tree are operands, such as constants or variable names, and the other nodes contain operators. This particular tree happens to be binary, because all the operators are binary, although this is the simplest case. It is possible for nodes to have more than two children. It is also possible for a node to have only one child, as is the case with the unary minus operator. In this assignment, you will design and implement an expression binary tree assuming that • there are only four operations: addition, subtraction, multiplication, and division • all operands are positive numbers • only Fully parenthesized algebraic expressions are used for testing To complete this assignment, you need to design a node, an expression tree, implement the design in Java, and test them in a driver program. Java is the required programming language for this assignment. If you need to review how to create an UML diagram or forget how to write comments in Javadoc style, see the examples in part III. The node class: A node contains a generic element, a reference to its left child, and a reference to its right child. It can’t be an inner class and it must have the following functionalities: • overloading constructors • getters/setters • other methods if any • overridden equals • overridden toString This node class must be a generic class. It will be used in the expression tree class or any classes where a node is required. When it is used in an expression tree, the element of a node can be an operand or an operator. The expression tree class: An expression tree object is a user-defined binary tree. It contains a reference to the tree (the root) and a reference to the associated expression- an infix. When requested, an expression tree can be visited in one of the three types of traversals, such as preorder traversal, inorder traversal, or postorder traversal. The best design for the tree traversals is to design a tree iterator, and use an iterator for traversals in an expression tree. To make it simpler for this assignment, we can simply include the traversal functionalities in the expression tree design. The following functionalitie