asked on

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!

ASKER CERTIFIED SOLUTION

heyhey_

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

diakov

//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