Solved

recursion problem

Posted on 1998-11-08
2
189 Views
Last Modified: 2010-03-30
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!
0
Comment
Question by:wazila
2 Comments
 
LVL 16

Accepted Solution

by:
heyhey_ earned 50 total points
ID: 1227094
     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
 
LVL 8

Expert Comment

by:diakov
ID: 1227095
//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

Featured Post

Windows Server 2016: All you need to know

Learn about Hyper-V features that increase functionality and usability of Microsoft Windows Server 2016. Also, throughout this eBook, you’ll find some basic PowerShell examples that will help you leverage the scripts in your environments!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

INTRODUCTION Working with files is a moderately common task in Java.  For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient.   However, when your application has vi…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question