Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# recursion problem

Posted on 1998-11-08
Medium Priority
196 Views
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
Question by:wazila
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 16

Accepted Solution

heyhey_ earned 200 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

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

}
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

## Featured Post

Question has a verified solution.

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

This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
###### Suggested Courses
Course of the Month8 days, 11 hours left to enroll