title: Binary expression tree converting postfix to infix and vice versa
body: <p>Task
  In this project, you are asked to develop a binary expression tree and use the tree to convert postfix and infix expressions to each other. An expression may contain 4 types of operators: multiplication (*), division (/), plus (+), and minus (-). We assume that multiplication and division have the same precedence, plus and minus have the same precedence, and multiplication and division have higher precedence than plus and minus. All operators are left-associative (i.e. associate left-to-right). Also, an expression might contain operands in the form of numbers (1, 129, ...) or alphabetic identifiers (a, x, var, ...).
  Binary Expression Tree: Build a binary expression tree class called "BET". Your BET class must have a nested class named "BinaryNode" to contain the node-related information (including, e.g., element and pointers to the children and parent nodes). You can choose any type for the element field of a BinaryNode. In addition, BET must at least support the following interface functions:</p>
  
  <p>Public interface:</p>
  
  <p>•<strong>BET()</strong> -- default zero-parameter constructor. Builds an empty tree. </p>
  
  <p>•<strong>BET(String expr, char mode)</strong> -- two-parameter constructor, where parameter "mode" specifies if "expr" is a string containing a postfix or infix expression. Possible values for "mode" are "p" for postfix and "i" for infix expressions. The tree should be built based on the expression. Tokens in the expression are separated by spaces. Ideally, this should be done by calling buildFromPostfix or buildFromInfix. If building the tree fails, throw an IllegalStateException. </p>
  
  <p>•<strong>bool buildFromPostfix(String postfix)</strong> -- parameter "postfix" is a string containing a postfix expression. The tree should be built based on the postfix expression. Tokens in the postfix expression are separated by spaces. If the tree contains nodes before the function is called, you need to first delete the existing nodes. Return true if the new tree is built successfully. Return false if an error is encountered.</p>
  
  <p>•<strong>bool buildFromInfix(String infix)</strong> -- parameter "infix" is string containing an infix expression. The tree should be built based on the infix expression. Tokens in the infix expression are separated by spaces. If the tree contains nodes before the function is called, you need to first delete the existing nodes. Return true if the new tree is built successfully. Return false if an error is encountered.</p>
  
  <p>•<strong>void printInfixExpression()</strong> -- Print out the infix expression of the current binary expression tree. Should do this by making use of the private (recursive) version</p>
  
  <p>•<strong>void printPostfixExpression()</strong> -- Print out the postfix expression of the current Binary Expression Tree. Use the private recursive function to help</p>
  
  <p>•<strong>int size()</strong> -- returns the number of nodes in the tree by using the private recursive function</p>
  
  <p>•<strong>bool isEmpty()</strong> -- returns true if the tree is empty</p>
  
  <p>•<strong>int leafNodes()</strong> -- Return the number of leaf nodes in the tree. (Use the private recursive function to help)</p>
  
  <p>Private helper functions (all the required private member functions must be implemented recursively):</p>
  
  <p>•<strong>void printInfixExpression(BinaryNode n)</strong>: print the corresponding fully parenthesized infix expression. You should not have unnecessary parentheses.</p>
  
  <p>•<strong>void makeEmpty(BinaryNode t)</strong>: delete all nodes in the tree with the root t.</p>
  
  <p>•<strong>void printPostfixExpression(BinaryNode n)</strong>: print the corresponding postfix expression.</p>
  
  <p>•<strong>int size(BinaryNode t)</strong>: return the number of nodes in the tree with the root t.</p>
  
  <p>•<strong>int leafNodes(BinaryNode t)</strong>: return the number of leaf nodes in the tree with the root t.</p>
  
  <p><strong>Postfix Notation</strong>: postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if  (exp1) op (exp2) is a normal fully parenthesized expression whose operation is op, the postfix version of this is pexp1 pexp2 op where pexp1 is the postfix version of exp1 and pexp2 is the postfix version of exp2. The postfix version of a single number or variable is just that number or variable. So, for example, the postfix version of <strong>((5+2) * (8-3))/4 is 5 2 + 8 3 - * 4 /</strong></p>
  
  <p><strong>Constructing BET from postfix expression</strong>: The basic operation of building a binary expression tree from a postfix expression is very simple. You just need one stack. Each time you encounter an operand (numbers, variables), create a tree node from it and push it on top of the stack. If you encounter an operator, just pop the top two operand nodes and push back a new tree node with the operator as the root and the two operands as its left and right children, into the stack. Once you have read every token from the expression, you should have one tree node in the stack which is the binary expression tree. If you have more or less than that, there has been an error in the expression.</p>
  
  <p><strong>Constructing BET from infix expression</strong>: The basic operation of building a binary expression tree from an infix expression (not necessarily parenthesized) is similar to that of evaluating arithmetic expressions. In this case, you need two stacks, one for operators and one for operands. Each time you read an operand in the expression push it on top of the operand stack. Each time you read an operator, push it on the operator stack, but first pop and create subtrees for all higher or equal precedence operators already on the stack. Each time you want to create a subtree for an operator, you pop the operator and two operands and make the operands left and right children of the operator. Then you will push the resulting subtree back on the operand stack. When you reach the end of the expression, do the same for all remaining operators on the operator stack. At the end, you should have an empty operator stack and only one tree node on the operand stack, which is the root of your binary expression tree.
  Converting postfix to Infix Expression:. To convert a postfix expression into an infix expression using a binary expression tree involves two steps. First, build a binary expression tree from the postfix expression. Second, print the nodes of the binary expression tree using an inorder traversal of the tree.</p>
  
  <p><strong>Converting infix to postfix Expression</strong>: To convert an infix expression into a postfix expression using a binary expression tree involves two steps. First, build a binary expression tree from the infix expression. Second, print the nodes of the binary expression tree using a postorder traversal of the tree.
  Note that during printing infix expressions, parentheses need to be added to ensure that the infix expression has the same value (and the same evaluation order) as the corresponding postfix expression and the binary expression tree. Your result should not add unnecessary parentheses. Tokens in an infix expression should also be separated by a space. The following are a few examples of postfix expressions and the corresponding infix expressions.</p>
  
  <pre><code>postfix expression  infix expression
  4 50 6 + +          ( 4 + ( 50 + 6 ) )
  4 50 + 6 +          ( ( 4 + 50 ) + 6 )
  4 50 + 6 2 * +        ( ( 4 + 50 ) + ( 6 * 2 ) )
  4 50 6 + + 2 *        ( ( 4 + ( 50 + 6 ) ) * 2 )
  a b + c d e + * *   ( ( a + b ) * ( c * ( d + e ) ) )
  </code></pre>
  
  <p>Also a driver program Main.java  has been included below. It is an example test program that will run some tests on your implementations.  However, your class will be tested with more than just this sample driver. It is recommended that you write other driver programs of your own, for more thorough testing. The output  of this test program is also included below.</p>
  
  <p>General Requirements
  •   Document your code appropriately so that it is readable and easy to navigate.
  •   For this project you can use ArrayList and Stack implementations in Java. (java.util.Stack, java.util.ArrayList)
  •   Any helper functions you write should be in the private section</p>
  
  <pre><code>  public static void main(String[] args) {
      try {
        System.out.println("\n\ntest1: a b c + * d -");
        BET test = new BET("a b c + * d -" , 'p');
        System.out.print("postfix: ");
        test.printPostfixExpression();
        System.out.print("infix: ");
        test.printInfixExpression();
        System.out.print("size: ");
        System.out.println(test.size());
        System.out.print("isEmpty: ");
        System.out.println(test.isEmpty());
        System.out.print("# of leaves: ");
        System.out.println(test.leafNodes());
        System.out.println("\n\ntest2: ( 3 + 2 ) * 3 + 1");
        test = new BET("( 3 + 2 ) * 3 + 1" , 'i');
        System.out.print("postfix: ");
        test.printPostfixExpression();
        System.out.print("infix: ");
        test.printInfixExpression();
        System.out.print("size: ");
        System.out.println(test.size());
        System.out.print("isEmpty: ");
        System.out.println(test.isEmpty());
        System.out.print("# of leaves: ");
        System.out.println(test.leafNodes());
        System.out.println("\n\ntest3: abc / 2 / f3 + z4 - 1 * 2");
        test.buildFromInfix("abc / 2 / f3 + z4 - 1 * 2");
        System.out.print("postfix: ");
        test.printPostfixExpression();
        System.out.print("infix: ");
        test.printInfixExpression();
        System.out.print("size: ");
        System.out.println(test.size());
        System.out.print("isEmpty: ");
        System.out.println(test.isEmpty());
        System.out.print("# of leaves: ");
        System.out.println(test.leafNodes());
        System.out.println("\n\ntest4: ( 3 + 2 * 3 + 1");
        test = new BET("( 3 + 2 * 3 + 1" , 'i');
        System.out.print("postfix: ");
        test.printPostfixExpression();
        System.out.print("infix: ");
        test.printInfixExpression();
        System.out.print("size: ");
        System.out.println(test.size());
        System.out.print("isEmpty: ");
        System.out.println(test.isEmpty());
        System.out.print("# of leaves: ");
        System.out.println(test.leafNodes());
      }
      catch(IllegalStateException e) {
  
        System.out.println(e.getMessage());
      }
    }
  }
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>test1: a b c + * d -
  postfix: a b c + * d -
  infix: ( ( a * ( b + c ) ) - d )
  size: 7
  isEmpty: false
  # of leaves: 4
  test2: ( 3 + 2 ) * 3 + 1
  postfix: 3 2 + 3 * 1 +
  infix: ( ( ( 3 + 2 ) * 3 ) + 1 )
  size: 7
  isEmpty: false
  # of leaves: 4
  test3: abc / 2 / f3 + z4 - 1 * 2
  postfix: abc 2 / f3 / z4 + 1 2 * -
  infix: ( ( ( ( abc / 2 ) / f3 ) + z4 ) - ( 1 * 2 ) )
  size: 11
  isEmpty: false
  # of leaves: 6
  test4: ( 3 + 2 * 3 + 1
  Invalid notation: ( 3 + 2 * 3 + 1
  </code></pre>