# recursion problem

the following code is recursive method i'm writing...
it walks through a binary tree that has stored a prefix expression such as (+ 2 (+2 3)) and is supposed to return it a infix expression like this (2 + (2 + 3)).

public String buildInfix(ETree pointer)
{
String myInfix ="";

if(pointer.getTypeOf() == 1)
{
ETree left = ((Internal)pointer).getLeft();
String store = buildInfix(left);
myInfix += "( " + store + " ";
myInfix += ((Character)((Internal)pointer).getObject()).charValue() + " ";
ETree right =((Internal)pointer).getRight();
store = buildInfix(right);
myInfix += store + " )";
return myInfix;
}

if(pointer.getTypeOf() == 2) //found a Constant
{
int temp =((Integer)((Constant)pointer).getObject()).intValue();
String number = "" + temp;
return number;
}

if(pointer.getTypeOf() == 3) //found a Variable
{
String temp =(String)((Variable)pointer).getObject();
return temp;
}

return myInfix;
}

when i use a simple expression such as (+ 2 4) it work perfectly fine and returns (2 + 4)
but if i make it complicated like (+2 (* 2 3)) then the function gets caught in a infinite loop...
i noticed this when i put in some print statements...the function gets hung on the 2 and the +...the pointers don't seem to move on to the next value...

does anyone know why????
i'd really appreciate the help...
thanks!
###### Who is Participating?

Commented:
it seems that your problem comes from the ETree definition, (or maybe example construction) so you'd better check the .getRight()      method
//          ETree right =((Internal)pointer).getRight();
(you haven't included ETree source !!!)

Sugestion:
why don't use more simple definition
class ETree {
int type;
Object value;
ETree left
ETree right
}

and you can use the value.toString() method instead of typecasting like mad.

"int temp =((Integer)((Constant)pointer).getObject()).intValue()"
"String number = "" + temp;"
(too much typecasting :( !!! too confusing for me. )

will change to
String number = pointer.value.toString();

(of course you can implement Get and Set methods instead of accessing internal fields directly ...)

hope this helps
heyhey
0

Commented:
//Take a look here:

//file ExpressionTester.java
public class ExpressionTester
{
public static void main(String[] argv)
{
//bulding (+ 2 (* 2 3))
ETree mult_two = new ETree(null, null, ETree.CONST, "2");
ETree mult_tree = new ETree(null, null, ETree.CONST, "3");
ETree mult = new ETree(mult_two, mult_tree, ETree.OP, "*");
ETree add_two = new ETree(null, null, ETree.CONST, "2");

}
public static String buildInfix(ETree p)
{
String result = "";

Integer t = p.getType();

if (t == ETree.CONST)
{
result = p.getValue();
}
else
{
if (t == ETree.VAR)
{
result = p.getValue();
}
else
{
if (t == ETree.OP)
{
result = "( " + buildInfix(p.getLeft()) + " " + p.getValue() + " " + buildInfix(p.getRight()) + " )";
}
else
{
System.out.println("Unexpected type!");
return "ERROR!!!";
}
}
}
return result;
}
public static String buildPrefix(ETree p)
{
String result = "";

Integer t = p.getType();

if (t == ETree.CONST)
{
result = p.getValue();
}
else
{
if (t == ETree.VAR)
{
result = p.getValue();
}
else
{
if (t == ETree.OP)
{
result = "( " + p.getValue() + " " + buildPrefix(p.getLeft()) + " " + buildPrefix(p.getRight()) + " )";
}
else
{
System.out.println("Unexpected type!");
return "ERROR!!!";
}
}
}
return result;
}
}

class ETree
{
private ETree left;
private ETree right;
private Integer type;

private String value;

//defining the constants for the type
public static final Integer OP = new Integer(1);
public static final Integer CONST = new Integer(2);
public static final Integer VAR = new Integer(3);

ETree(ETree left, ETree right, Integer type, String value)
{
this.left = left;
this.right = right;
this.type = type;
this.value = value;
}
public Integer getType()
{
return type;
}
public ETree getLeft()
{
return left;
}
public ETree getRight()
{
return right;
}
public String getValue()
{
return value;
}
}

Cheers,
Nik
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.