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!
wazilaAsked:
Who is Participating?
 
heyhey_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
 
diakovCommented:
//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");
      ETree add = new ETree(add_two, mult, ETree.OP, "+");

      System.out.println(buildInfix(add));
      System.out.println(buildPrefix(add));
  }
  public static String buildInfix(ETree p)
  {
    String result = "";

    Integer t = p.getType();

      //allways start with the recursion terminating conditions
      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();

      //allways start with the recursion terminating conditions
      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.

All Courses

From novice to tech pro — start learning today.