1. Use Java to implement your solution.

OBJECTIVE:

1. Understand the application of Trees.
2. Create an implementation of the Binary Tree ADT using a linked tree structure.

OVERVIEW

Arithmetic expressions such as

2 * (9 / -3)

have an inherent tree-like structure. For example, Figure A is a representation of the expression in Equation (1). This kind of tree is called an expression tree.

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (2, 9, 3). The non-terminal nodes of an expression tree are the operators (*, / and -). Notice that the parentheses which appear in Equation (1) do not appear in the tree. Nevertheless, the tree representation has captured the intent of the parentheses since the subtraction is lower in the tree than the multiplication.

Figure A: Tree representing the expression 2 * (9 / -3).

The common arithmetic operators are either unary or binary. For example, addition, subtraction, multiplication, and division are all binary operations and negation is a unary operation. Therefore, the non-terminal nodes of the corresponding expression trees have either one or two non-empty subtrees. That is, expression trees are usually binary trees.

QUESTIONS:

Create an expression tree program that reads a prefix* arithmetic expression and displays it in a binary tree form. Assume that the expression consists of single-digit, nonnegative integers (0 to 9) and four basic arithmetic operators (+, -, *, and /). Further, assume that the arithmetic expression is input from the keyboard with all the characters on one line.

Then, using traversal techniques display the arithmetic expression in preorder, inorder and postorder notations. Finally evaluates the expression and output the result. Display suitable messages.

* This question only constraint user to input prefix notation, however if you wish to enable input of regular arithmetic expression with brackets (e.g (9*3)-(20/5)), you may apply Stack ADT to convert it to other notations before building the expression tree.

2 9 3