Application #2

Write a program that takes a postfix expression and produces a binary expression tree. You can assume that the postfix expression is a string that has only binary operators and one-letter operands.

Modify PostfixTree.java file. Follow steps #1 - #7 included in the file.

The expected output of your finished program is as follow:

The first postfix expression is:

ab*c+

The inorder traversal is:

a * b + c

The postorder traversal is:

a b * c +

The second postfix expression is:

ab-c*def-+g/+

The inorder traversal is:

a - b * c + d + e - f / g

The postorder traversal is:

a b - c * d e f - + g / +

public class PostfixTree { private BinaryNode root; private final static String OPERATORS = "+-*/"; public PostfixTree() { this.root = null; } // end default constructor public PostfixTree(String postfix) { // TODO Project 2  // This secondary constructor creates the postfix tree // stack to put partial expressions on Stack> exprStack = new Stack<>(); // #1 repeat for every character in the postfix { // #2 create subExpression tree of type BinaryNode with the current character // #3 if the current character is an operator // #3a get the operands from the stack // #3b build up the subExpression by setting the left and right // subtrees to the appropriate operands removed from the stack // #4 push subExpression on the stack } // #5 At the end of it all the entire expression should be the // top expression on the stack, so remove it from the stack // and point root to it. // Note: that the input postfix string and the postorder output // should be the same. } // end constructor public void inOrderTraversal() { inOrder(this.root); System.out.println(); } // end inOrderTraversal private void inOrder(BinaryNode node) { if (node != null) { inOrder(node.getLeftChild()); System.out.print(node.getData() + " "); inOrder(node.getRightChild()); } // end if } // end inOrder public void postOrderTraversal() { // TODO Project 2  System.out.println("You need to implement me - postOrderTraversal()"); } // end postOrderTraversal private void postOrder(BinaryNode node) { // TODO Project 2  System.out.println("You need to implement me - postOrder()"); } // end postOrder public static void main(String[] args) { String expression = "ab*c+"; System.out.println("The first postfix expression is: " + expression); PostfixTree tree = new PostfixTree(expression); System.out.println(" The inorder traversal is:"); tree.inOrderTraversal(); System.out.println(" The postorder traversal is:"); tree.postOrderTraversal(); // . . . expression = "ab-c*def-+g/+"; System.out.println(" The second postfix expression is: " + expression); tree = new PostfixTree(expression); System.out.println(" The inorder traversal is:"); tree.inOrderTraversal(); System.out.println(" The postorder traversal is:"); tree.postOrderTraversal(); } // end main } // end PostfixTree