Please make sure the main method and the output same as given. Please make sure it works.

///////////////////////////////////

Write a program that transforms a postfix expression into a tree such as that shown in Figure 8.11 in this chapter. Youll need to modify the Tree class from the tree.java program (Listing 8.1) and the ParsePost class from the postfix.java program (Listing 4.8) in Chapter 4. There are more details in the discussion of Figure 8.11.

After the tree is generated, traversals of the tree will yield the prefix, infix, and postfix equivalents of the algebraic expression. The infix version will need parentheses to avoid generating ambiguous expressions. In the inOrder() method, display an opening parenthesis before the first recursive call and a closing parenthesis after the second recursive call.

-------------------------------------------

Reference for 8.1

// tree.java // demonstrates binary tree // to run this program: C>java TreeApp import java.io.*; import java.util.*; // for Stack class //////////////////////////////////////////////////////////////// class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this nodes left child public Node rightChild; // this nodes right child public void displayNode() // display ourself { System.out.print({); System.out.print(iData); System.out.print(, ); System.out.print(dData); System.out.print(} ); } } // end class Node //////////////////////////////////////////////////////////////// class Tree { private Node root; // first node of tree // ------------------------------------------------------------- public Tree() // constructor { root = null; } // no nodes in tree yet

// ------------------------------------------------------------- public Node find(int key) // find node with given key { // (assumes non-empty tree) Node current = root; // start at root while(current.iData != key) // while no match, { if(key

else if(isLeftChild) parent.leftChild = null; // disconnect else // from parent parent.rightChild = null; } // if no right child, replace with left subtree else if(current.rightChild==null) if(current == root) root = current.leftChild; else if(isLeftChild) parent.leftChild = current.leftChild; else parent.rightChild = current.leftChild; // if no left child, replace with right subtree else if(current.leftChild==null) if(current == root) root = current.rightChild; else if(isLeftChild) parent.leftChild = current.rightChild; else parent.rightChild = current.rightChild; else // two children, so replace with inorder successor { // get successor of node to delete (current) Node successor = getSuccessor(current); // connect parent of current to successor instead if(current == root) root = successor; else if(isLeftChild) parent.leftChild = successor; else parent.rightChild = successor; // connect successor to currents left child successor.leftChild = current.leftChild; } // end else two children // (successor cannot have a left child)

return true; // success } // end delete() // ------------------------------------------------------------- // returns node with next-highest value after delNode // goes to right child, then right childs left descendents private Node getSuccessor(Node delNode) { Node successorParent = delNode; Node successor = delNode; Node current = delNode.rightChild; // go to right child while(current != null) // until no more { // left children, successorParent = successor; successor = current; current = current.leftChild; // go to left child } // if successor not if(successor != delNode.rightChild) // right child, { // make connections successorParent.leftChild = successor.rightChild; successor.rightChild = delNode.rightChild; } return successor; } // ------------------------------------------------------------- public void traverse(int traverseType) { switch(traverseType) { case 1: System.out.print( Preorder traversal: ); preOrder(root); break; case 2: System.out.print( Inorder traversal: ); inOrder(root); break; case 3: System.out.print( Postorder traversal: ); postOrder(root); break; } System.out.println(); }

// ------------------------------------------------------------- private void preOrder(Node localRoot) { if(localRoot != null) { System.out.print(localRoot.iData + ); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); } } // ------------------------------------------------------------- private void inOrder(Node localRoot) { if(localRoot != null) { inOrder(localRoot.leftChild); System.out.print(localRoot.iData + ); inOrder(localRoot.rightChild); } } // ------------------------------------------------------------- private void postOrder(Node localRoot) { if(localRoot != null) { postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); System.out.print(localRoot.iData + ); } } // ------------------------------------------------------------- public void displayTree() { Stack globalStack = new Stack(); globalStack.push(root); int nBlanks = 32; boolean isRowEmpty = false; System.out.println( ......................................................); while(isRowEmpty==false) {

Stack localStack = new Stack(); isRowEmpty = true; for(int j=0; j

public static void main(String[] args) throws IOException { int value; Tree theTree = new Tree(); theTree.insert(50, 1.5); theTree.insert(25, 1.2); theTree.insert(75, 1.7); theTree.insert(12, 1.5); theTree.insert(37, 1.2); theTree.insert(43, 1.7); theTree.insert(30, 1.5); theTree.insert(33, 1.2); theTree.insert(87, 1.7); theTree.insert(93, 1.5); theTree.insert(97, 1.5); while(true) { System.out.print(Enter first letter of show, ); System.out.print(insert, find, delete, or traverse: ); int choice = getChar(); switch(choice) { case s: theTree.displayTree(); break; case i: System.out.print(Enter value to insert: ); value = getInt(); theTree.insert(value, value + 0.9); break; case f: System.out.print(Enter value to find: ); value = getInt(); Node found = theTree.find(value); if(found != null) { System.out.print(Found: ); found.displayNode(); System.out.print( );

} else System.out.print(Could not find ); System.out.print(value + ); break; case d: System.out.print(Enter value to delete: ); value = getInt(); boolean didDelete = theTree.delete(value); if(didDelete) System.out.print(Deleted + value + ); else System.out.print(Could not delete ); System.out.print(value + ); break; case t: System.out.print(Enter type 1, 2 or 3: ); value = getInt(); theTree.traverse(value); break; default: System.out.print(Invalid entry ); } // end switch } // end while } // end main() // ------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } // ------------------------------------------------------------- public static char getChar() throws IOException { String s = getString(); return s.charAt(0); } //------------------------------------------------------------- public static int getInt() throws IOException

{ String s = getString(); return Integer.parseInt(s); } // ------------------------------------------------------------- } // end class TreeApp ////////////////////////////////////////////////////////////////

4.8 class ParsePost for reference

//////////////////////////////////////////////////////////////// class ParsePost { private StackX theStack; private String input; //-------------------------------------------------------------- public ParsePost(String s) { input = s; } //-------------------------------------------------------------- public int doParse() { theStack = new StackX(20); // make new stack char ch; int j; int num1, num2, interAns; for(j=0; j= 0 && ch

break; case *: interAns = num1 * num2; break; case /: interAns = num1 / num2; break; default: interAns = 0; } // end switch theStack.push(interAns); // push result } // end else } // end for interAns = theStack.pop(); // get answer return interAns; } // end doParse() } // end class ParsePost

Please make sure in this JAVA program the main method is same as given. Please don't repost any answer that's already given in chegg. Thanks

/* You need to write classes Node, Tree, ParsePost, and Post TreeApR with main method */ public static void main(String[] args) throws IOException ParsePost pp; Tree theTree = null; while(true) System.out.print("enter, show, or traverse: "); int choice- getChar); switch(choice) case 'e' System.out print("Enter a postfix expression (AB+): "); String str = getString(); pp new ParsePost(str); theTree pp.doParse): break; case s the Tree.displayTree); break; case 't System.out.print("Enter type 1, 2 or 3:"); int value-getInt); the Tree.traverse(value); break; default: System.out print("Invalid entry n"); l/ end switch // end while ,//end main() Your output may look like: enter, show, or traverse: e Enter a postfix expression (AB+): ABC+* enter, show, or traverse: s /* You need to write classes Node, Tree, ParsePost, and Post TreeApR with main method */ public static void main(String[] args) throws IOException ParsePost pp; Tree theTree = null; while(true) System.out.print("enter, show, or traverse: "); int choice- getChar); switch(choice) case 'e' System.out print("Enter a postfix expression (AB+): "); String str = getString(); pp new ParsePost(str); theTree pp.doParse): break; case s the Tree.displayTree); break; case 't System.out.print("Enter type 1, 2 or 3:"); int value-getInt); the Tree.traverse(value); break; default: System.out print("Invalid entry n"); l/ end switch // end while ,//end main() Your output may look like: enter, show, or traverse: e Enter a postfix expression (AB+): ABC+* enter, show, or traverse: s