Binary tree? help!

[Ana]

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.

[doredson]

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).

[Murdoctor]

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.

[Murdoctor]

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(")");

}

[Ana]

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.

[Murdoctor]

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);
}