Binary tree? help!


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 6 of 6

Thread: Binary tree? help!

  1. #1
    Join Date
    Nov 2004
    Location
    Newark, New Jersey
    Posts
    38

    Wink Binary tree? help!

    I have a problem with this code. Is working ok but now I want the infix method to give an output using the minimum number of parentheses. I don't know if you understand what I want, but here is a copy of the program and its output. only need the infix method to used parentheses properly.


    /**
    * A class containing a couple of methods for traversing binary
    * expression trees
    *
    * @author Ana
    * @version 1.0
    */
    public class PrintTree
    {
    public BinaryTree root;

    /**
    * Use a postorder traversal to print an expression tree in
    * postfix form
    *
    * @param exprTree the expression to be printed
    */
    public static void asPostfix(BinaryTree exprTree)
    {
    if (!exprTree.isEmpty()) {
    PrintTree.asPostfix(exprTree.left());
    PrintTree.asPostfix(exprTree.right());
    System.out.print(exprTree.value() + " ");
    }
    }
    /**
    * Use an inorder traversal to print an expression tree in
    * infix form (properly parenthesized)
    *
    * @param exprTree the expression to be printed
    */

    public static void asInfix(BinaryTree exprTree)
    {

    if(!exprTree.isEmpty()){
    PrintTree.asInfix(exprTree.left());
    System.out.print(exprTree.value() + " ");
    PrintTree.asInfix(exprTree.right());

    }
    }


    }

    ex:
    if I use the input: (2 * (3 + (4 + 8)))*(7 + (3))
    with the code that I have right now I get the output: infix: 2 * 3 + 4 + 8* 7 + 3

    but I want the outout to be like:
    infix: 2 * (3 + 4 + 8) * (7 + 3)

    THANK YOU FOR YOUR HELP.
    Last edited by Ana; 12-10-2004 at 01:35 AM.

  2. #2
    Join Date
    Nov 2004
    Location
    Minnesota
    Posts
    99
    hard to say exactly the flaw without the rest of the code. Seems like you need an if statement somewhere that inserts parends depending on the operator that links 2 operands (children of the current node).

  3. #3
    Join Date
    Dec 2004
    Posts
    6

    Re: Binary tree? help!

    Originally posted by Ana
    I want the infix method to give an output using the minimum number of parentheses.
    Getting the "minimum" number of parentheses will be a little tricky, since you'd need to keep track of the unfolding of the tree to see where the groupings should be made.

    If you just want to have a correct output without the minimization, you can put parentheses around any addition/subtraction operation (overkill, but it will work). Basically, if the "value" of the tree node is "+" or "-", then print a "(" before traversing the left branch, and a ")" after traversing the right branch. That will give you a fully-parenthesized output that will be a correct infix notification, but wouldn't be minimal.

    Then, minimizing the parens would be a little extra work, since you'd have to either know where you've been or where you are going in the unfolding of the tree. I would suggest passing along an extra boolean "state" in the recursive traversal procedure. Set it to FALSE initially, but pass in TRUE on the recursive calls iff the operator (node value) is "*" or "/". Then, when you find an operator (node value) that is "+" or "-", print the parentheses (as I described above) iff the state passed in is TRUE, signifying that you are doing an addition/subtraction as a sub-operation within a multiplication or division expression, which would necessitate parentheses.

  4. #4
    Join Date
    Dec 2004
    Posts
    6

    Re: Re: Binary tree? help!

    Example (untested, coding as I type):

    public static void asInfix(BinaryTree exprTree, boolean inMultOrDiv)
    {

    if(!exprTree.isEmpty()){

    boolean nextState = (exprTree.value().equals("*") || exprTree.value().equals("/"));

    boolean printParen = (inMultOrDiv && (exprTree.value().equals("+") || exprTree.value().equals("-"));

    if (printParen) System.out.print("(");
    PrintTree.asInfix(exprTree.left(), nextState);
    System.out.print(exprTree.value() + " ");
    PrintTree.asInfix(exprTree.right(), nextState);
    if (printParen) System.out.print(")");

    }

  5. #5
    Join Date
    Nov 2004
    Location
    Newark, New Jersey
    Posts
    38
    I think that that code might work if only it uses only one parameter becuase the hide main program (I don't have access to it) uses only one parameter( Binary exprTree).
    But I don't now how can I do that. thank you for your help.

    Help me please! to write a code using only one parameter.

  6. #6
    Join Date
    Dec 2004
    Posts
    6
    Originally posted by Ana
    Help me please! to write a code using only one parameter.
    Just call the two-parameter method from the one-parameter method:

    public static void asInfix(BinaryTree exprTree)
    {
    asInfix(exprTree, FALSE);
    }

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center