This assignment you will work on a binary tree $($not binary search tree$)$ to represent mathematical

formulas and printing the tree.

ALGEBRAIC EXPRESSIONS

An algebraic expression can be represented using three different notations:

Infix: The most conventional way to write an expression is called infix notation. The arithmetic

operators appear in between two operands. e$.$g$.4-3*2+1$

Prefix: In prefix notation, as the name suggests, operators come before the operands.

e$.$g$.*-43+21$

Postfix: In postfix notation, different from infix and prefix notations, operators come after the

operands. e$.$g$.43-21+*$

One use of the binary trees in computer science is to represent algebraic expressions. In an algebraic

expression tree, each leaf node contains an operand and a non$-$leaf node, including the root node,

contains an operator that is applied to the results of its left and right sub$-$trees. For example, the

expression below:

$(4-3)**(2+1)$

can be represented :

Figure $1-$

PART I $-$ BUILD TREE

In this part you will build an algebraic expression tree using the binary tree data structure. The data

structure will represent a single math formula given in postfix notation $($e$.$g$.$ the formula in Figure $1$ in

postfix form is: $43-12+**)$

For simplicity you may assume the following:

The postfix expression contains single digit integers $(0.\mathrm{.}9)$ and four operations $(+,-,*,/)$

In an expression, no whitespace is allowed between characters.

You can use the Node class below to start writing your program:

class Node char

char c;

public Node $($char c$)$ i

this. $c=c$

this.c $=c$; this.left $=$ this.right $=$ null

$\}$

Write a static method "buildTree" that takes a string formula written in postfix notation, then builds

a binary tree $($Figure $1)$ for that formula and returns the root node of the tree.

public static Node buildTree$($ String formulaInPostfix $)\{dots\}$

PART II $-$ PRINT TREE

Write a static method "printTree" which takes the root node of a tree and prints the three as shown in

the examples below:

public static void printTree$($ Node root $)\{dots\}$

HINTS

Think about using a stack while reading the formula character by character.

e$.$g$.$ Stack$=$