Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Feb 26th, 2012  |  syntax: Java  |  size: 6.54 KB  |  views: 27  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /**
  2.    The infixPrint() method takes a BTree that is an expression tree
  3.    and converts it into a String with infix notation that is properly
  4.    parenthesized.
  5.  
  6.    The expression tree can contain the following five binary operators,
  7.       +, -, *, /, ^
  8.    and two unary operators
  9.       neg, sqrt.
  10.    The unary operators have their operand in their right subtree.
  11.  
  12.    The unary operator "neg" should be printed out as a minus sign, "-".
  13.  
  14.    The unary operator "sqrt" should be printed out as "sqrt( )" with
  15.    parentheses around its operand.
  16.  
  17.    The binary operators should be printed with a space on either side of
  18.    them, except for the "^" operator. Since it has such high precedence,
  19.    it is easier to read if this operator does not have spaces around it.
  20.  
  21.    You can assume that the expression tree in not empty and that it
  22.    is properly formed (it doesn't have any "syntax errors").
  23. */
  24.  
  25. /*
  26.  * 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 :)
  27.  * 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.
  28.  * Read my comment on PrettyPrinter for why I needed to add functions.
  29.  * */
  30.  
  31. public class InfixPrinter
  32. {
  33.    /**
  34.       This inlinePrint() method is essentially an
  35.       inorder traversal of the tree.
  36.    */
  37.    public static String infixPrint(BTree tree)
  38.    {
  39.      
  40.       String result = "";
  41.      
  42.       if (precedence(tree.getLeftElement()) !=0 && precedence(tree.getRightElement()) == 0 && precedence(tree.getElement()) !=0) // operand, operand, constant
  43.       {
  44.         if (precedence(tree.getLeftElement()) > precedence(tree.getElement())) // left element has higher precedence then parent
  45.         {
  46.           result += "(" + infixPrint(tree.getLeftTree()) + ") " + tree.getElement() + " " + tree.getRightElement();
  47.         }
  48.         else
  49.         {
  50.           result += infixPrint(tree.getLeftTree()) + " " + tree.getElement() + " " + tree.getRightElement();
  51.         }
  52.       }
  53.      
  54.      
  55.      
  56.       else if (precedence(tree.getRightElement()) !=0 && precedence(tree.getLeftElement()) == 0
  57.                  && precedence(tree.getElement()) !=0) // constant, operand, operand
  58.       {
  59.         if (precedence(tree.getRightElement()) >= precedence(tree.getElement())) // right element has higher precedence then parent
  60.         {
  61.           result += tree.getLeftElement() + " " + tree.getElement() + " (" + infixPrint(tree.getRightTree()) + ")";
  62.         }
  63.         else
  64.         {
  65.           result += tree.getLeftElement() + " " + tree.getElement() + " " + infixPrint(tree.getRightTree());
  66.         }
  67.       }
  68.      
  69.      
  70.      
  71.      
  72.       else if (precedence(tree.getLeftElement()) != 0 && precedence(tree.getElement()) !=0 && precedence(tree.getRightElement()) !=0) // operand, operand, operand,
  73.       {
  74.        if (precedence(tree.getLeftElement()) >= precedence (tree.getElement()) && precedence (tree.getElement()) > precedence(tree.getRightElement())) // left higher than or equal to parent, right lower than parent
  75.        {
  76.          result += "(" + infixPrint(tree.getLeftTree()) + ") " + tree.getElement() + " " + infixPrint(tree.getRightTree());
  77.        }
  78.        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
  79.        {
  80.          result += "(" + infixPrint(tree.getLeftTree()) + ") " + tree.getElement() + " (" + infixPrint(tree.getRightTree()) + ")";
  81.        }
  82.        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
  83.        {
  84.          result +=infixPrint(tree.getLeftTree()) + " " + tree.getElement() + " (" + infixPrint(tree.getRightTree()) + ")";
  85.        }
  86.        else if (precedence(tree.getLeftElement()) < precedence (tree.getElement()) && precedence (tree.getElement()) > precedence(tree.getRightElement())) // left lower than parent, right lower than parent
  87.        {
  88.          result +=infixPrint(tree.getLeftTree()) + " " + tree.getElement() + " " + infixPrint(tree.getRightTree());
  89.        }
  90.        
  91.       }
  92.      
  93.      
  94.        
  95.       else if (precedence(tree.getRightElement()) == 0 && precedence(tree.getLeftElement()) == 0 && tree.getRightTree() != null && tree.getLeftTree() != null ) // constant, anything, constant
  96.       {
  97.         result += tree.getLeftElement() + " " + tree.getElement() + " " + tree.getRightElement();
  98.       }
  99.      
  100.       else if (precedence(tree.getLeftElement()) == 0 && tree.getRightTree() == null) // constant, anything, null
  101.       {
  102.         result += tree.getLeftElement() + " " + tree.getElement();
  103.       }
  104.      
  105.       else if (precedence(tree.getRightElement()) == 0 && tree.getLeftTree() == null) // constant, anything, null
  106.       {
  107.         result += tree.getElement() + " " + tree.getRightElement();
  108.       }
  109.    
  110.       else if (precedence(tree.getElement()) == 0 && precedence(tree.getLeftElement()) != 0 && precedence(tree.getRightElement()) != 0)
  111.         result += " parent node is constant, left child and right child are operators.";
  112.       else if (precedence(tree.getElement()) == 0 && precedence(tree.getLeftElement()) != 0 && precedence(tree.getRightElement()) == 0)
  113.         result += " parent node is a constant, left is an operator, right is a constant.";
  114.       else if (precedence(tree.getElement()) == 0 && precedence(tree.getLeftElement()) == 0 && precedence(tree.getRightElement()) != 0)
  115.         result += " parent node is a constant, left is a constant, right is an operator.";
  116.        
  117.        
  118.  
  119.  
  120.  
  121.       return result;
  122.    }//infixPrint()
  123.  
  124.  
  125.    // http://www.java-tips.org/java-se-tips/java.lang/what-is-java-operator-precedence.html
  126.    // http://introcs.cs.princeton.edu/java/11precedence/
  127.    public static int precedence(String op)
  128.    {
  129.       int result = 0;  // "highest" precedence (i.e., constants)
  130.  
  131.       if ( op.equals("sqrt") )
  132.       {
  133.          result = 1;
  134.       }
  135.       if ( op.equals("^") )
  136.       {
  137.          result = 2;
  138.       }
  139.       else if ( op.equals("neg") )
  140.       {
  141.          result = 3;
  142.       }
  143.       else if ( op.equals("*")
  144.              || op.equals("/") )
  145.       {
  146.          result = 4;
  147.       }
  148.       else if ( op.equals("+")
  149.              || op.equals("-") )
  150.       {
  151.          result = 5;
  152.       }
  153.  
  154.       return result;
  155.    }//precedence()
  156.  
  157. }//PrettyPrinter
clone this paste RAW Paste Data