/**
   The infixPrint() method takes a BTree that is an expression tree
   and converts it into a String with infix notation that is properly
   parenthesized.

   The expression tree can contain the following five binary operators,
      +, -, *, /, ^
   and two unary operators
      neg, sqrt.
   The unary operators have their operand in their right subtree.

   The unary operator "neg" should be printed out as a minus sign, "-".

   The unary operator "sqrt" should be printed out as "sqrt( )" with
   parentheses around its operand.

   The binary operators should be printed with a space on either side of
   them, except for the "^" operator. Since it has such high precedence,
   it is easier to read if this operator does not have spaces around it.

   You can assume that the expression tree in not empty and that it
   is properly formed (it doesn't have any "syntax errors").
*/

/*
 * if you happened to read prettyprinter before this, you'll know I added functions to BTree. If you didn't... I added function to BTree :)
 * Hope it's ok, it's was the best way I could figure out some stuff and so I didn't think it would be wrong thing to do.
 * Read my comment on PrettyPrinter for why I needed to add functions.
 * */

public class InfixPrinter
{
   /**
      This inlinePrint() method is essentially an
      inorder traversal of the tree.
   */
   public static String infixPrint(BTree tree)
   {

      String result = "";

      if (precedence(tree.getLeftElement()) !=0 && precedence(tree.getRightElement()) == 0 && precedence(tree.getElement()) !=0) // operand, operand, constant
      {
        if (precedence(tree.getLeftElement()) > precedence(tree.getElement())) // left element has higher precedence then parent
        {
          result += "(" + infixPrint(tree.getLeftTree()) + ") " + tree.getElement() + " " + tree.getRightElement();
        }
        else
        {
          result += infixPrint(tree.getLeftTree()) + " " + tree.getElement() + " " + tree.getRightElement();
        }
      }



      else if (precedence(tree.getRightElement()) !=0 && precedence(tree.getLeftElement()) == 0
                 && precedence(tree.getElement()) !=0) // constant, operand, operand
      {
        if (precedence(tree.getRightElement()) >= precedence(tree.getElement())) // right element has higher precedence then parent
        {
          result += tree.getLeftElement() + " " + tree.getElement() + " (" + infixPrint(tree.getRightTree()) + ")";
        }
        else
        {
          result += tree.getLeftElement() + " " + tree.getElement() + " " + infixPrint(tree.getRightTree());
        }
      }




      else if (precedence(tree.getLeftElement()) != 0 && precedence(tree.getElement()) !=0 && precedence(tree.getRightElement()) !=0) // operand, operand, operand,
      {
       if (precedence(tree.getLeftElement()) >= precedence (tree.getElement()) && precedence (tree.getElement()) > precedence(tree.getRightElement())) // left higher than or equal to parent, right lower than parent
       {
         result += "(" + infixPrint(tree.getLeftTree()) + ") " + tree.getElement() + " " + infixPrint(tree.getRightTree());
       }
       else if (precedence(tree.getLeftElement()) >= precedence (tree.getElement()) && precedence (tree.getElement()) <= precedence(tree.getRightElement())) // left higher than or equal to parent, right higher than or equal to parent
       {
         result += "(" + infixPrint(tree.getLeftTree()) + ") " + tree.getElement() + " (" + infixPrint(tree.getRightTree()) + ")";
       }
       else if (precedence(tree.getLeftElement()) < precedence (tree.getElement()) && precedence (tree.getElement()) <= precedence(tree.getRightElement())) // left lower than parent, right higher than or equal to parent
       {
         result +=infixPrint(tree.getLeftTree()) + " " + tree.getElement() + " (" + infixPrint(tree.getRightTree()) + ")";
       }
       else if (precedence(tree.getLeftElement()) < precedence (tree.getElement()) && precedence (tree.getElement()) > precedence(tree.getRightElement())) // left lower than parent, right lower than parent
       {
         result +=infixPrint(tree.getLeftTree()) + " " + tree.getElement() + " " + infixPrint(tree.getRightTree());
       }

      }



      else if (precedence(tree.getRightElement()) == 0 && precedence(tree.getLeftElement()) == 0 && tree.getRightTree() != null && tree.getLeftTree() != null ) // constant, anything, constant
      {
        result += tree.getLeftElement() + " " + tree.getElement() + " " + tree.getRightElement();
      }

      else if (precedence(tree.getLeftElement()) == 0 && tree.getRightTree() == null) // constant, anything, null
      {
        result += tree.getLeftElement() + " " + tree.getElement();
      }

      else if (precedence(tree.getRightElement()) == 0 && tree.getLeftTree() == null) // constant, anything, null
      {
        result += tree.getElement() + " " + tree.getRightElement();
      }

      else if (precedence(tree.getElement()) == 0 && precedence(tree.getLeftElement()) != 0 && precedence(tree.getRightElement()) != 0)
        result += " parent node is constant, left child and right child are operators.";
      else if (precedence(tree.getElement()) == 0 && precedence(tree.getLeftElement()) != 0 && precedence(tree.getRightElement()) == 0)
        result += " parent node is a constant, left is an operator, right is a constant.";
      else if (precedence(tree.getElement()) == 0 && precedence(tree.getLeftElement()) == 0 && precedence(tree.getRightElement()) != 0)
        result += " parent node is a constant, left is a constant, right is an operator.";





      return result;
   }//infixPrint()


   // http://www.java-tips.org/java-se-tips/java.lang/what-is-java-operator-precedence.html
   // http://introcs.cs.princeton.edu/java/11precedence/
   public static int precedence(String op)
   {
      int result = 0;  // "highest" precedence (i.e., constants)

      if ( op.equals("sqrt") )
      {
         result = 1;
      }
      if ( op.equals("^") )
      {
         result = 2;
      }
      else if ( op.equals("neg") )
      {
         result = 3;
      }
      else if ( op.equals("*")
             || op.equals("/") )
      {
         result = 4;
      }
      else if ( op.equals("+")
             || op.equals("-") )
      {
         result = 5;
      }

      return result;
   }//precedence()

}//PrettyPrinter