Results 1 to 2 of 2
  1. #1
    roaan is offline Member
    Join Date
    Jul 2009
    Posts
    6
    Rep Power
    0

    Default Creating a tree of depth 5

    I am doing this problem where in i have to create a tree of max depth 5. Trees of arithmetic expressions. I have classes Node, Binop, Plus, Minus, Multiply, Divide, OperatorFactory, Terminal Factory, and a main class. But what is happening currently is that the trees that are created are of some size (max 2 depth) and mostly it throws stack overflow error. To add child to the tree i have a method addRandomKids in BinOp which is supposed to add children to the trees. The code for the different classes is as follows:

    [insert]
    Java Code:
    // Node.java
     
    import java.util.Random;
     
    /* Generated by Together */
     
    public abstract class Node implements Cloneable 
    {
    	public int depth = 0;
        abstract void setChild(int position, Node n);
        abstract double eval(double[] data);
        
        public String toString()
        {
        	return "";
        }
        
        abstract void addRandomKids(OperatorFactory o, TerminalFactory t,int maxDepth, Random rand);
        
        public Object clone()
        {
        	Object o = null;
        	try
        	{
        		o = super.clone();
        	}
        	catch(CloneNotSupportedException e){
        		e.printStackTrace();
        	}
        	
        	return o;
        }
    }
     
     
    // BinOp.java
     
    import java.util.Random;
     
    public class Binop extends Node{
        
        protected Node lChild, rChild;
        public Binop() {}
        
        public Binop(Node l, Node r)
        {
        	lChild = l; rChild = r;
        }
       
        public void setChild(int position, Node n) 
        {
            if (position == 1)
            	lChild = n;
            else
                rChild = n;
        }
        
        public void addRandomKids(OperatorFactory o, TerminalFactory t,int maxDepth, Random rand)
        {
        	if(depth == maxDepth)
        	{
        		this.setChild(1,t.getTerminal(rand));
        		this.setChild(2,t.getTerminal(rand));
        		return;
        	}
        	else{
        		
        		int i = rand.nextInt(4);
        		if(i < 3){
        			Node lChild = o.getOperator(rand);
        			++depth;
        			lChild.addRandomKids(o, t, maxDepth, rand);
        			depth = 0;
        			Node rChild = o.getOperator(rand);
        			++ depth;
        			rChild.addRandomKids(o, t, maxDepth, rand);
        		}
        		else
        		{
        			this.setChild(1,t.getTerminal(rand));
            		this.setChild(2,t.getTerminal(rand));
            		return;
        		}
        	}
        }
     
    	@Override
    	double eval(double[] data) {
    		// TODO Auto-generated method stub
    		return 0;
    	}
        
    }
     
    // OperatorFactory.java
     
    import java.util.Random;
     
     
    public class OperatorFactory {
     
    	private Node[] n;
     
    	OperatorFactory(Node[] node) {
    		n = node;
    	}
     
    	public Node getOperator(Random rand) {
    		Node op = null;
    		int r = rand.nextInt(4);
    		switch (r) {
     
    		case 0:
    			op = n[0];
    			break;
    		case 1:
    			op = n[1];
    			break;
    		case 2:
    			op = n[2];
    			break;
    		case 3:
    			op = n[3];
    			break;
    		}
    		return op;
    	}
    }
     
    // TerminalFactory.java
     
    import java.util.Random;
     
    public class TerminalFactory {
     
    	private int numIndepVars = 3;
     
    	TerminalFactory(int nIndVars) {
    		numIndepVars = nIndVars;
    	}
     
    	public Node getTerminal(Random rand) {
    		
    		// Choose a random number between 0 and numIndepVars
    		// if less than numIndepVars return Variable else return Constant
    		int r = rand.nextInt(numIndepVars)+ 1;
    		if (r < numIndepVars) {
    			Variable var = new Variable(r);
    			return var;
    		} else {
    			double dble = rand.nextDouble();
    			Const con = new Const(dble);
    			return con;
    		}
    	}
    }
     
    // Plus.java (Same sort of files for Minus, Mult, Divide as well)
     
    /* Generated by Together */
     
    public class Plus extends Binop {
        public Plus() {}
        
        public Plus(Node l, Node r) {
            super(l, r);
        }
        
        public double eval(double[] data) {
            return lChild.eval(data) + rChild.eval(data);
        }
        
        public String toString() {
            String s = new String();
            s += "(" + lChild.toString() + " + " + rChild.toString() + ")";
            return s;
        }
        
    }
     
    // Variable.java
     
    import java.util.Random;
     
    /* Generated by Together */
     
    public class Variable extends Node{
        private int index;
        public Variable(int i) {
            index = i;
        }
    	public void setChild(int position, Node n) {
            System.out.println("Attempt to add child to Variable");
        }
        public String toString() {
            String s = new String();
            s += "X" + index;
            return s;
        }
    	public double eval(double[] data) {
            if (index < data.length)
            	return data[index];
            else {
                System.out.println("Variable index exceeds data array length.");
                return 0;
            }
        }
    	
    	public void addRandomKids(OperatorFactory o, TerminalFactory t,int maxDepth, Random rand){}
     
    }
     
    // Const.java
     
    import java.util.Random;
     
    /* Generated by Together */
     
    public class Const extends Node {
        private double value;
        public Const(double d) {value = d; }
        public void setChild(int position, Node n) {}
        public double eval(double[] data) { return value; }
        public String toString() {
            String s = new String();
            s += value;
            return s;
        }
        
        public void addRandomKids(OperatorFactory o, TerminalFactory t,int maxDepth, Random rand){}
     
    }
     
     
    // Main class
     
    import java.util.Random;
     
    public class TestAlgebra 
    {
    	static int numIndepVars = 3;
    	static int maxDepth = 5;
    	static Random rand = new Random();
    	
    	public static void main(String[] args) 
    	{
    	    double[] data = new double[3];
    	    data[0] = 3.14;
    	    data[1] = 2.78;
    	    data[2] = 1.0;
    	    
    	    Node[] ops = {new Plus(), new Minus(), new Mult(),new Divide()};
    	    OperatorFactory o = new OperatorFactory(ops);
    	    TerminalFactory t = new TerminalFactory(numIndepVars);
    	    
    	    Node root = o.getOperator(rand);
    	    root.addRandomKids(o, t, maxDepth, rand);
    	    String s = root.toString();
    	    System.out.println(s + " = " + root.eval(data));
    	}
    }
    Also posted at:forums.sun.com/thread.jspa?threadID=5397104&tstart=0]New To Java - Creating a tree of depth 5

  2. #2
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    7

    Default

    i find that you initialize depth to 0 in Binop.java
    there should be a problem, as some other nodes will start with depth = 0

Similar Threads

  1. B tree
    By wide in forum New To Java
    Replies: 2
    Last Post: 07-01-2009, 12:37 AM
  2. maximum view depth?
    By Bit2_Gosu in forum New To Java
    Replies: 0
    Last Post: 02-16-2009, 03:32 PM
  3. Recursion depth in java
    By poulius in forum New To Java
    Replies: 17
    Last Post: 01-11-2009, 02:38 PM
  4. Replies: 0
    Last Post: 04-09-2008, 07:44 PM
  5. Creating a tree
    By Preethi in forum AWT / Swing
    Replies: 0
    Last Post: 01-07-2008, 02:04 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •