Thread: nary tree from string

hey all,

I am trying to create a nary tree from string following some rules.

It takes the stored character string as input and generates an output tree. We keep on pushing alphabets onto stack and start popping the stack as soon as we encounter a closing parenthesis. The topmost element of the stack is then made the child of the second topmost element and so on. The variable count is used when a single node contains data made up of multiple characters.





MakeNarrayTree (string)

{

Repeat till ‘\0’ is not encountered

Read alphanumeric character one at a time.

If (read alphanumeric character! = “)”)

{

Push it into stack.

}

If (read alphanumeric character==”)”)

{

Create a node last

Create another node temp

Take an array for storing intermediate nodes.



Do

{

Last =temp

Pop temp from the stack

If( temp == “(“)

{

Break;

}

Add temp into array

} while (true);

Make last as parent of all the nodes in the array[size-1]

Push last into stack

}

Make last as root node of tree

}





What has to be done is :



Read sentence.

Pick up the bracketed form of rule from the rule database. eg (ROOT(S(VP(VB LT)(ADVP LT))(VP(PP(NP X)))))

MakeNaryTree for rule as described



Please correct the algo if it is wrong. A sample code would be really appreciated.
I have created a generic nary tree( and ofcourse nodes) using lists & arraylists but what it does is really generic in nature. ...


Regards,
Alex

I have tried implementing the algo... but i m sure somewhere something is seriously wrong..
It is giving me ArrayIndexOutOfBoundsException

Please check if I have implemented the algo properly or if the algo is wrong..

  import java.util.ArrayList; import java.util.List; import java.util.*; /** * * @author User1 */ public class narytree {   /** * @param x * @param args the command line arguments */ArrayList a1 = new ArrayList();   public void makenary(char[] x) {     String s1=""; int i =0;   while (x[i]!='\0') { if (x[i]!=')') {     Node n1=new Node(); n1.setData(x[i]); a1.add(n1); } if (x[i]==')') {     Node temp =new Node();Node temp2 =new Node(""); do {   Object last = a1.get(a1.size()-1); temp=(Node)last; a1.remove(a1.size()-1);   if(temp.getData()=="(") { break; } int p = a1.size();   Object get2 = a1.get(p-1);   temp2=(Node)get2; temp2.addChild(temp); }while(true);   for (int k=0;i<(a1.size()-1);k++) { Node temp4 =new Node(""); temp4=(Node)a1.get(k); temp4.setParent(temp2); }   a1.add(temp2); } i++; } }         public static void main(String[] args) { narytree n1 = new narytree(); char x[]={'S','(','V','P','(','V','B','L','T',')','(','A','D','V','P','(','R','B','L','T',')',')',')','\0'}; n1.makenary(x); /* Node<String> root = new Node<>("S");*/ Object get2 = n1.a1.get(n1.a1.size()-1); Node tempn = new Node(); tempn=(Node)get2;   Tree<String> tree = new Tree<>(tempn);   //ArrayList<Node<String>> preOrder = tree.getLongestPathFromRootToAnyLeaf(); System.out.println(tree.getRoot()); //System.out.println(tree.getNumberOfNodes()); //System.out.println(tree.getNumberOfDescendants(root)); // System.out.println(tree.getPreOrderTraversal());   }   }

Thanks & Regards

Originally Posted by DuncanS

Where are you incrementing i? The -1 access error seems to indicate that your Array size is 0 when you try to access it, and your OutOfMemory error seems to indicate that your for loop never ends since your condition checks against a value that is never incremented.

oops.. it should have been k instead of i.. (thanks)

  import java.util.ArrayList; import java.util.List; import java.util.*; /** * * @author User1 */ public class NaryTree {   /** * @param x * @param args the command line arguments */ArrayList a1 = new ArrayList();   public void makenary(char[] x) {     String s1=""; int i =0;   while (x[i]!='\0') { if (x[i]!=')') {     Node n1=new Node(); n1.setData(x[i]); a1.add(n1); } if (x[i]==')') {     Node temp =new Node();Node temp2 =new Node(""); do {   Object last = a1.get(a1.size()-1); temp=(Node)last; a1.remove(a1.size()-1);   if(temp.getData()=="(") { break; } int p = a1.size(); while (p>0) { Object get2 = a1.get(p-1);   temp2=(Node)get2; temp2.addChild(temp); } }while(true);   for (int k=0;k<(a1.size()-1);k++) { Node temp4 =new Node(""); temp4=(Node)a1.get(k); temp4.setParent(temp2); }   a1.add(temp2); } i++; } } public static void main(String[] args) { NaryTree n1 = new NaryTree(); char x[]={'S','(','V','P','(','V','B','L','T',')','(','A','D','V','P','(','R','B','L','T',')',')',')','\0'}; n1.makenary(x);   Object get2 = n1.a1.get(n1.a1.size()-1); Node tempn = new Node(); tempn=(Node)get2;   Tree<String> tree = new Tree<>(tempn);     System.out.println(tree.getRoot());     }   }

java.lang.OutOfMemoryError: Java heap space at aryTree.makenary(NaryTree.java:54)

which is :

temp2.addChild(temp);

My node.java file is :

  import java.util.ArrayList; import java.util.List;   public class Node<T> {	private T data;	private List<Node<T>> children;	private Node<T> parent; public Node() {	this.data = null;	this.children = new ArrayList<Node<T>>();	}    	public Node(T data) {	this.data = data;	this.children = new ArrayList<Node<T>>();	}  	public Node(Node<T> node) {	this.data = (T) node.getData();	children = new ArrayList<Node<T>>();	}  	public void addChild(Node<T> child) {	child.setParent(this);	children.add(child);	}  	public void addChildAt(int index, Node<T> child) {	child.setParent(this);	this.children.add(index, child);	}  	public void setChildren(List<Node<T>> children) {	for (Node<T> child : children)	child.setParent(this);  	this.children = children;	}  	public void removeChildren() {	this.children.clear();	}  	public Node<T> removeChildAt(int index) {	return children.remove(index);	}    	public void removeThisIfItsAChild(Node<T> childToBeDeleted)	{	List <Node<T>> list = getChildren();	list.remove(childToBeDeleted);	}  	public T getData() {	return this.data;	}  	public void setData(T data) {	this.data = data;	}  	public Node<T> getParent() {	return this.parent;	}  	public void setParent(Node<T> parent) {	this.parent = parent;	}  	public List<Node<T>> getChildren() {	return this.children;	}  	public Node<T> getChildAt(int index) {	return children.get(index);	}  	@Override	public boolean equals(Object obj) {	if (null == obj)	return false;  	if (obj instanceof Node) {	if (((Node<?>) obj).getData().equals(this.data))	return true;	}  	return false;	}  	@Override	public String toString() {	return this.data.toString();	}   }

I don't actually want anybody to write the algo for me but correct it if it is wrong. I think I might be overlooking my mistakes.


Thanks and Regards

The out of memory error is caused because you never decrease p. Use --p instead of p - 1 here:

Object get2 = a1.get(p-1);

The ArrayOutOfBounds exception is because your break condition never triggers because you are misusing generics. To apply a bandaid, use

if (temp.getData().equals('(')) { break; }

instead of what you have.

Thanks for correcting, Now I am getting the correct root but the children of the tree are all the characters.
Considering the character array

char x[]={'S','(','V','P','(','V','B','L','T',')','(','A','D','V','P','L','T',')',')','(','V','P','(','P','P','(','N','P','X',')',')',')','\0'};

the children that are shown are

[T, L, B, V, T, T, L, L, P, P, V, V, D, D, A, A, S, S, S, P, V, X, X, P, P, N, N, S, S, P, P, P, P, S, S, P, P, V, V]

with the root appearing 7 times as child!

import java.util.ArrayList; import java.util.List; import java.util.*; /** * * @author User1 */ public class NaryTree {   /** * @param x * @param args the command line arguments */ArrayList a1 = new ArrayList();   public void makenary(char[] x) {       int i =0;   while (x[i]!='\0') { if (x[i]!=')') { Node n1=new Node();   n1.setData(x[i]); a1.add(n1); } if (x[i]==')') {     Node temp =new Node();Node temp2 =new Node(""); do {   Object last = a1.get(a1.size()-1); temp=(Node)last; a1.remove(a1.size()-1);   if (temp.getData().equals('(')) { break; } int p = a1.size(); while (p>0) { Object get2 = a1.get(--p);   temp2=(Node)get2; temp2.addChild(temp); } }while(true);   for (int k=0;k<(a1.size()-1);k++) { Node temp4 =new Node(""); temp4=(Node)a1.get(k); temp4.setParent(temp2); }   a1.add(temp2); } i++; } } public static void main(String[] args) { NaryTree n1 = new NaryTree(); // char x[]={'S','(','V','P','(','V','B','L','T',')','(','A','D','V','P',' ','L','T',')',')','(','V','P','(','P','P','(','N','P',' ','X',')',')',')','\0'}; char x[]={'S','(','V','P','(','V','B','L','T',')','(','A','D','V','P','L','T',')',')','(','V','P','(','P','P','(','N','P','X',')',')',')','\0'}; n1.makenary(x);   Object get2 = n1.a1.get(n1.a1.size()-1); Node tempn = new Node(); tempn=(Node)get2;   Tree<String> tree = new Tree<>(tempn);   //ArrayList<Node<String>> preOrder = tree.getLongestPathFromRootToAnyLeaf(); System.out.println(tree.getRoot()); System.out.println(tree.getRoot().getChildren()); System.out.println(tree.getRoot().getChildren().size()); //System.out.println(tree.getNumberOfNodes()); //System.out.println(tree.getNumberOfDescendants(root)); //System.out.println(tree.getPreOrderTraversal());   }   }

tree.java

import java.util.ArrayList;   public class Tree<T> {  	private Node<T> root;  	public Tree(Node<T> root) {	this.root = root;	}  	public boolean isEmpty() {	return (root == null);	}  	public Node<T> getRoot() {	return root;	}  	public void setRoot(Node<T> root) {	this.root = root;	}  	public boolean exists(T key) {	return find(root, key);	}  	public int getNumberOfNodes() {	return getNumberOfDescendants(root) + 1;	}  	public int getNumberOfDescendants(Node<T> node) {	int n = node.getChildren().size();	for (Node<T> child : node.getChildren())	n += getNumberOfDescendants(child);  	return n;  	}  	private boolean find(Node<T> node, T keyNode) {	boolean res = false;	if (node.getData().equals(keyNode))	return true;  	else {	for (Node<T> child : node.getChildren())	if (find(child, keyNode))	res = true;	}  	return res;	}   private Node<T> findNode(Node<T> node, T keyNode) {	if(node == null)	return null;	if(node.getData().equals(keyNode))	return node;	else	{	Node<T> cnode = null;	for (Node<T> child : node.getChildren())	if ((cnode = findNode(child, keyNode)) != null)	return cnode;	}	return null; }  	public ArrayList<Node<T>> getPreOrderTraversal() {	ArrayList<Node<T>> preOrder = new ArrayList<Node<T>>();	buildPreOrder(root, preOrder);	return preOrder;	}  	public ArrayList<Node<T>> getPostOrderTraversal() {	ArrayList<Node<T>> postOrder = new ArrayList<Node<T>>();	buildPostOrder(root, postOrder);	return postOrder;	}  	private void buildPreOrder(Node<T> node, ArrayList<Node<T>> preOrder) {	preOrder.add(node);	for (Node<T> child : node.getChildren()) {	buildPreOrder(child, preOrder);	}	}  	private void buildPostOrder(Node<T> node, ArrayList<Node<T>> preOrder) {	for (Node<T> child : node.getChildren()) {	buildPreOrder(child, preOrder);	}	preOrder.add(node);	}  	public ArrayList<Node<T>> getLongestPathFromRootToAnyLeaf() {	ArrayList<Node<T>> longestPath = null;	int max = 0;	for (ArrayList<Node<T>> path : getPathsFromRootToAnyLeaf()) {	if (path.size() > max) {	max = path.size();	longestPath = path;	}	}	return longestPath;	}  	public int getMaxDepth()	{	return getLongestPathFromRootToAnyLeaf().size();	}  	public ArrayList<ArrayList<Node<T>>> getPathsFromRootToAnyLeaf() {	ArrayList<ArrayList<Node<T>>> paths = new ArrayList<ArrayList<Node<T>>>();	ArrayList<Node<T>> currentPath = new ArrayList<Node<T>>();	getPath(root, currentPath, paths);  	return paths;	}  	private void getPath(Node<T> node, ArrayList<Node<T>> currentPath,	ArrayList<ArrayList<Node<T>>> paths) {	if (currentPath == null)	return;  	currentPath.add(node);  	if (node.getChildren().size() == 0) {	// This is a leaf	paths.add(clone(currentPath));	}	for (Node<T> child : node.getChildren())	getPath(child, currentPath, paths);  	int index = currentPath.indexOf(node);	for (int i = index; i < currentPath.size(); i++)	currentPath.remove(index);	}  	private ArrayList<Node<T>> clone(ArrayList<Node<T>> list) {	ArrayList<Node<T>> newList = new ArrayList<Node<T>>();	for (Node<T> node : list)	newList.add(new Node<T>(node));  	return newList;	}     }

My ultimate aim is to get the tree as :

IMG3.jpg

from the string : S(VP(VB LT)(ADVP LT))(VP(PP(NP X)))

I know I am asking for a lot, but I seek your guidance.

Thanks and Regards

Why I am getting ArrayIndexOutOfBoundsException:37 at Line 23 ?

import java.util.ArrayList; import java.util.List; import java.util.*; /** * * @author User1 */ public class Ntree {   /** * @param x * @param args the command line arguments */ArrayList a1 = new ArrayList();   public void makenary(char[] x) {       int i =0;   while (x[i]!='\0') // Line 23   { String s1=""; while (x[i]!='(') { while (x[i]!=')') { if (x[i]!='(') { s1=s1+x[i];   } else{break;} i++; // System.out.println(s1); } while (x[i]==')') { Object last = a1.get(a1.size()-1); Node temp=(Node)last; a1.remove(a1.size()-1); Object last2 = a1.get(a1.size()-1); Node temp2=(Node)last2; temp2.addChild(temp); // temp.setParent(temp2); a1.remove(a1.size()-1); a1.add(temp2);   i++;   }   if (x[i]!=')') break; else i++;   }   Node n1=new Node(); n1.setData(s1); // System.out.println(n1.getData()); a1.add(n1);   i++;   } for(int ii = 0; ii < a1.size(); ii++) { System.out.println((a1.get(ii))); } } public static void main(String[] args) {   char z[]={'S','(','V','P','(','V','B','L','T',')','(','A','D','V','P','(','R','B','(','L','T',')',')','(','V','P','(','P','P','(','N','P','X',')',')',')','\0'}; Ntree n = new Ntree(); n.makenary(z);     }   }

Posting the full text of errors you want help with is always appreciated and usually an opportunity to learn something.

Your code is experiencing the error because there is no check to ensure the array index does not exceed the last index in the array and prevent it from happening. This is often done in a for() loop, capping the loop control variable used as the index at < array.length. Since your error is occurring within a while() loop, you could add the check to the while() loop condition, preventing the loop from executing if in an out-of-bounds condition, or somewhere inside the loop, breaking out of the loop.

Thnx Greg, did the corrections. One more thing though,

My code :

import java.util.ArrayList; import java.util.List; import java.util.*; /** * * @author User1 */ public class Ntree {   /** * @param x * @param args the command line arguments */ArrayList a1 = new ArrayList();     public void makenary(char[] x) {       int i =0;   while (x[i]!='\0') // Line 23   { String s1=""; while (x[i]!='(') { while (x[i]!=')') { if (x[i]!='(') { s1=s1+x[i];     } else{break;} i++;   } while (x[i]==')') { Object last = a1.get(a1.size()-1); Node temp=(Node)last; a1.remove(a1.size()-1); Object last2 = a1.get(a1.size()-1); Node temp2=(Node)last2; temp2.addChild(temp); // temp.setParent(temp2); a1.remove(a1.size()-1); a1.add(temp2);   i++;   }   if (x[i]!=')') break; else i++;   }   Node n1=new Node(); // System.out.println("string"+s1+"end"); // System.out.println("length"+s1.length()); n1.setData(s1); // System.out.println(n1.getData());   a1.add(n1);   while (i<a1.size()) i++;   } for(int ii = 0; ii < a1.size(); ii++) { System.out.println((a1.get(ii))); } } public static void main(String[] args) {   char z[]={'S','(','V','P','(','V','B','L','T',')','(','A','D','V','P','(','R','B','(','L','T',')',')','(','V','P','(','P','P','(','N','P','X',')',')',')','\0'}; Ntree n = new Ntree(); n.makenary(z);     }   }

It is giving the output :

S   VP   VBLT             ADVP         RB LT             VP     NPX

Actually, it is adding empty strings and the node data is set with the empty strings and eventually my arraylist shows it as its elements. What to do to eliminate the empty strings getting added to the node or list so that I get the output as :

S VP VBLT ADVP RB LT VP NPX

Thanks

--- Update ---

Never mind, I did it : //line 74

for(int ii = 0; ii < a1.size(); ii++) { while(a1.get(ii).toString().length()==0) { a1.remove(ii); }   System.out.println((a1.get(ii))); // System.out.println((a1.get(ii))); }

Do let me know if same thing can be achieved through better means...


Thanx..