String to Binary Tree and vice versa

[jakko100]

Hello almighty Java gurus,

I have a little task and I have no thoughts at all anymore. I must convert a string ( like A(B,C) or A(B(C,D), E(F)) ) that represents a left-representation of binary tree. I must convert into a object and after that turn it around - I must make a right-representation of a string from object.

I made a class below:

import java.util.*;

public class kodutoo_5 implements Enumeration<kodutoo_5> {
private String name;
private kodutoo_5 firstChild;
private kodutoo_5 nextSibling;

kodutoo_5(String n, kodutoo_5 d, kodutoo_5 r) {
setName(n);
setNextSibling(d);
setFirstChild(r);
}

kodutoo_5() {
this("", null, null);
}

kodutoo_5(String n) {
this(n, null, null);
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public kodutoo_5 getFirstChild() {
return firstChild;
}

public void setFirstChild(kodutoo_5 firstChild) {
this.firstChild = firstChild;
}

public kodutoo_5 getNextSibling() {
return nextSibling;
}

public void setNextSibling(kodutoo_5 nextSibling) {
this.nextSibling = nextSibling;
}

public String toString() {
return getName();
}

public boolean hasMoreElements() {
return (getNextSibling() != null);
}

public kodutoo_5 nextElement() {
return getNextSibling();
}

public Enumeration<kodutoo_5> child() {
return getFirstChild();
}

private static kodutoo_5 addChild(kodutoo_5 parent, kodutoo_5 current, String nodeString) {
kodutoo_5 result = current;

//kui alluvaid ei ole, siis jarelikult juurtipp
if(parent.getFirstChild() == null) {
//lisame alluva
parent.setFirstChild(new kodutoo_5(nodeString));
result = parent.getFirstChild();
//alluvaid on
} else {
result.setNextSibling(new kodutoo_5(nodeString));
result = result.getNextSibling();
}

return result;
}

public static kodutoo_5 parseTree(String s) {
kodutoo_5 emptyRoot = new kodutoo_5();
parseTree(emptyRoot, s, 0);

return emptyRoot.getFirstChild();
}

private static int parseTree(kodutoo_5 parent, String s, int position) {
kodutoo_5 current = null;
StringBuilder nodeVal = new StringBuilder();

//alustame string parsimist
for (int i = position; i < s.length(); i++) {
//kui leiame '('
if (s.charAt(i) == '(') {
if (nodeVal.length() > 0) {
current = addChild(parent, current, nodeVal.toString());
nodeVal = new StringBuilder();
}

i = parseTree(current, s, i + 1);
//kui leiame ')'
} else if (s.charAt(i) == ')') {
if (nodeVal.length() > 0) {
current = addChild(parent, current, nodeVal.toString());
nodeVal = new StringBuilder();
}

return i;
//kui leiame ','
} else if (s.charAt(i) == ',') {
if (nodeVal.length() > 0) {
current = addChild(parent, current, nodeVal.toString());
nodeVal = new StringBuilder();
}
//kui on elemendi sisu
} else {
nodeVal.append(s.charAt(i));
}
}

if (nodeVal.length() > 0) {
current = addChild(parent, current, nodeVal.toString());
}

return s.length();
}

public String rightParentheticRepresentation() {
StringBuilder sb = new StringBuilder();

//kontrollime kas juurtipp eksisteerib
if (getName() == null) {
throw new NullPointerException("Puud ei eksisteeri!");
}

//kontrollime ega juurtipp tuhi ei ole
if (getName() == "") {
throw new RuntimeException("Puud ei eksisteeri!");
}

//juurtipp eksisteerib, jarelikult ka puu
if (getFirstChild() != null) {
sb.append("(");
sb.append(getFirstChild().rightParentheticRepresentation());
Enumeration<kodutoo_5> child = child();

while (child.hasMoreElements()) {
sb.append(",");
child = child.nextElement();
sb.append(((kodutoo_5) child).rightParentheticRepresentation());
}

sb.append(")");
}

sb.append(getName());

return sb.toString();
}

public static void main(String[] args) {
String s1 = "A(B,C)";
String s2 = "A(B(C,D),E(F))";

kodutoo_5 t1 = kodutoo_5.parseTree(s1);
kodutoo_5 t2 = kodutoo_5.parseTree(s2);

String v1 = t1.rightParentheticRepresentation();
String v2 = t2.rightParentheticRepresentation();

System.out.println(s1 + " ==> " + v1);
System.out.println(s2 + " ==> " + v2);
}
}



It work's like a charm, but my teacher won't accept this, because he's wants to see that I'm using StringTokenizer class in parseTree method. So I started to rebuild my class and ended up here:


import java.util.*;

public class kodutoo_5 implements Enumeration<kodutoo_5> {
private String name;
private kodutoo_5 firstChild;
private kodutoo_5 nextSibling;

kodutoo_5(String n, kodutoo_5 d, kodutoo_5 r) {
setName(n);
setNextSibling(d);
setFirstChild(r);
}

kodutoo_5() {
this("", null, null);
}

kodutoo_5(String n) {
this(n, null, null);
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public kodutoo_5 getFirstChild() {
return firstChild;
}

public void setFirstChild(kodutoo_5 firstChild) {
this.firstChild = firstChild;
}

public kodutoo_5 getNextSibling() {
return nextSibling;
}

public void setNextSibling(kodutoo_5 nextSibling) {
this.nextSibling = nextSibling;
}

public String toString() {
return getName();
}

public boolean hasMoreElements() {
return (getNextSibling() != null);
}

public kodutoo_5 nextElement() {
return getNextSibling();
}

public Enumeration<kodutoo_5> child() {
return getFirstChild();
}

private static kodutoo_5 addChild(kodutoo_5 parent, kodutoo_5 current, String nodeString) {
kodutoo_5 result = current;

//kui alluvaid ei ole, siis jarelikult juurtipp
if(parent.getFirstChild() == null) {
//lisame alluva
parent.setFirstChild(new kodutoo_5(nodeString));
result = parent.getFirstChild();
//alluvaid on
} else {
result.setNextSibling(new kodutoo_5(nodeString));
result = result.getNextSibling();
}

return result;
}

public static kodutoo_5 parseTree(String s) {
kodutoo_5 emptyRoot = new kodutoo_5();
parseTree(emptyRoot, s);

return emptyRoot.getFirstChild();
}

private static void parseTree(kodutoo_5 parent, String s) {

kodutoo_5 current = null;
StringTokenizer st = new StringTokenizer(s, "(),", true);
StringBuilder sb = new StringBuilder();


while(st.hasMoreTokens()) {
String element = st.nextToken();
if(element.compareTo("(") == 0) {
if(sb.length() > 0) {
current = addChild(parent, current, sb.toString());
sb = new StringBuilder();
}
} else if(element.compareTo(")") == 0) {
if(sb.length() > 0) {
current = addChild(parent, current, sb.toString());
sb = new StringBuilder();
}
} else if(element.compareTo(",") == 0) {
if(sb.length() > 0) {
current = addChild(parent, current, sb.toString());
sb = new StringBuilder();
}
} else {
sb.append(element);
}
}

if(sb.length() > 0) {
current = addChild(parent, current, sb.toString());
}
}

public String rightParentheticRepresentation() {
StringBuilder sb = new StringBuilder();

//kontrollime kas juurtipp eksisteerib
if (getName() == null) {
throw new NullPointerException("Puud ei eksisteeri!");
}

//kontrollime ega juurtipp tuhi ei ole
if (getName() == "") {
throw new RuntimeException("Puud ei eksisteeri!");
}

//juurtipp eksisteerib, jarelikult ka puu
if (getFirstChild() != null) {
sb.append("(");
sb.append(getFirstChild().rightParentheticRepresentation());
Enumeration<kodutoo_5> child = child();

while (child.hasMoreElements()) {
sb.append(",");
child = child.nextElement();
sb.append(((kodutoo_5) child).rightParentheticRepresentation());
}

sb.append(")");
}

sb.append(getName());

return sb.toString();
}

public static void main(String[] args) {
String s1 = "A(B,C)";
//String s2 = "A(B(C,D),E(F))";

kodutoo_5 t1 = kodutoo_5.parseTree(s1);
//kodutoo_5 t2 = kodutoo_5.parseTree(s2);

String v1 = t1.rightParentheticRepresentation();
//String v2 = t2.rightParentheticRepresentation();

System.out.println(s1 + " ==> " + v1);
//System.out.println(s2 + " ==> " + v2);
}
}



But I can't make it right. Can anybody help me out to make this code work, please?

[dlorde]

... my teacher won't accept this, because he's wants to see that I'm using StringTokenizer class in parseTree method.

That's interesting, because Sun now say StringTokenizer is a 'legacy' class, discourage its use, and recommend you use String.split(..) or the regex package classes instead (check out the API docs (http://java.sun.com/javase/6/docs/api/java/util/StringTokenizer.html)) :rolleyes:

Teachers open the door, but you must enter by yourself...
Chinese proverb

[jakko100]

I think I had a hard times to make this first version of my class to work. Why can't you point me, what's I'm doing wrong in second version? I need to use StringTokenizer class, however.

[jakko100]

Anyone?

[keang]

You can't just say it doesn't work and expect someone to fix it for you. You have to explain in detail what is happening and what you expected to happen.

But before to do that do a manual run through of the working method and see what happens and then repeat the exercise for the broken one and you will see where the logic differs. By manual run through I mean choose some input values and look at the code line by line executing each line as you go. It can also be helpful to use a pencil and paper to jot down the variable values after each line has executed.

[jakko100]

If you think that I'm hoping you to post code here, you wrong. I just hoped that maybe you specialists point me, what I'm missing here or what I'm done wrong. In words, not in code. I'm tried to fix this code and debugged it already week or so. I posted here, so I can teach something, but maybe it's all about nagging. Sorry for interrupting!

And thanks for teaching and helping...

[dlorde]

If you provide the information requested, we may be able to help - if not, meh.

Computers are like bikinis. They save people a lot of guesswork...
Sam Ewing