program.java

这是用遗传编程算法来拟合曲线的一个经典程序

/*作者：徐朝*/
/*[e-mail]*/
package kernel;
/**
*所有节点的基类
*/
public abstract class Program 
{
	public String symbol;//代表该节点的字符串
	public Program SubItems[];        //该函数的下级节点 
	Program parent; //指向父节点
	int no; //节点的编号
	int noFunction;//只算非叶子节点时的编号
	int index;//如果节点在SubItems里，那么其下标值存于此

    //返回节点值,为了通用性起见，返回一对象
	abstract public Object eval();

	/**
	* 返回该子树节点数量,如果OnlyFunction设置为true,则只计算非叶节点的数量
	*/
	abstract public int countNodes(boolean OnlyFunction);


	/**
	* 对子树进行深度拷贝并返回对象
	*/
	abstract public Object DeepClone();	
	
	//用先根遍历的方法显示树的方法1

    public String displayTree(Program p)
    {
    	String s = "";
    	if(p != null)
    	{
   		
    		if(p.SubItems != null)
    		{
    			s = s + "(" + p.symbol + " ";
    			for(int i=0; i < p.SubItems.length; i++) 
                {
                	s = s + " ";
                    s = s + displayTree(p.SubItems[i]);
                    s = s + " ";
                }
                s = s + ")";
                return s;
            } 
            else
            {
            	s = s + p.symbol;
            	return s;
            }
            
    	}
    	else
    	    return s;         
    }
    //设置每个节点指向父节点的指针,以及为每个节点编号，并将节点在SubItems里的
    //下标设置一下。
    //在为每个节点编号时，设置两种编号，一种是把所有节点都算进来的编号no，另一种是不算
    //叶节点的编号noFunction，以利于后面使用
    //其中count树组中只有一个元素，这用来作为全局变量存储计数
    void setParent(Program p,int[] count,int [] countFunction)
    {    	
    	p.no = count[0];
    	count[0]++;	
    	if(p != null)
    	{
    		if(p.SubItems != null)
    		{
    			//如果该节点有下级节点，证明该节点不是叶子节点故计算编号noFunction
    			p.noFunction = countFunction[0];
    			countFunction[0]++;
    			for(int i = 0; i < p.SubItems.length; i++)
    			{
    				p.SubItems[i].parent = p;
    				p.SubItems[i].index = i;
    				setParent(p.SubItems[i], count, countFunction);
    			}
    		}
    	}
    }
    
    //设置每个节点指向父节点的指针,以及为每个节点编号
    public void setParent()
    {
    	int [] count = {1};
    	int [] countFunction = {1};
    	this.parent = null; //根节点的父节点为空
    	setParent(this,count, countFunction);    	
    }
    

    //显示树,isNo代表是否显示编号,isFunction代表是否显示函数编号
    public String toString(boolean isNo,boolean isFunction)
    {
    	setParent();
    	String str =  displayTree1(this, isNo, isFunction);
    	return str;
    }
    public String toString(boolean isNo)
    {
    	return toString(isNo, false);
    }
    public String toString()
	{
		return displayTree(this);
	}
    String getMargin(Program p,boolean isFirst)
    {
         if(p.parent == null)
             return "";
         else
         {
             //a的父节点中最后一个孩子的下标
             int lastChild = p.parent.SubItems.length - 1;
             //thisChild表示a节点在父节点中孩子节点里的下标值
             int thisChild = 0;
             for(int i = 0; i < p.parent.SubItems.length; i++)
             {
                 if(p.parent.SubItems[i].equals(p))
                     thisChild= i;
             }
             if(isFirst) //如果是第一次使用该方法
                 //如果节点a是父节点的最后一个孩子节点
                 if( lastChild == thisChild)
                     return getMargin(p.parent,false) + "└→";
                 else
                     return getMargin(p.parent,false) + "├→";
             else
                 if( lastChild == thisChild)
                     return getMargin(p.parent,false) + " ";
                 else
                     return getMargin(p.parent,false) + "│ ";
        }

    }
    //显示某树节点,isNo代表是否显示编号,isFunction代表是否显示函数编号
    String displayNode(Program p, boolean isNo, boolean isFunction)
    {
    	String str = getMargin(p, true) + p.symbol;
    	if(isNo)
           str = str + "(" + p.no + ")";
        if(isFunction)
           str = str + "(" + p.noFunction + ")";           
        str = str + "\n";
        return str;
    }
    //用先根遍历的方法显示树的方法2, ,isNo代表是否显示编号,isFunction代表是否显示函数编号
    String displayTree1(Program p, boolean isNo, boolean isFunction)
    {
    	String str = "";
        if(p != null)
        {
           str = str + displayNode(p, isNo, isFunction);
           if(p.SubItems != null)
           {
               for(int i=0; i < p.SubItems.length; i++)
                   str = str + displayTree1(p.SubItems[i], isNo, isFunction);
           }
       }
       return str;
   }
   //用广度优先搜索查找语法树中编号为no的节点，并返回引用
   //如果isFunction为真，则
    //获得语法树中非叶子节点编号为no的节点的引用    

   Program indexOf(int no,boolean isFunction)
   {
   	   if(this.no == no && !isFunction)
   	       return this;
   	   if(this.noFunction == no && isFunction)
   	       return this;
   	   Queue queue = new Queue();
   	   queue.enq(this);
   	   Program p;
   	   while(!queue.isEmpty())
   	   {
   	   	    p = (Program)(queue.front());
   	   	    if(p.SubItems != null)
   	   	    {
   	   	    	for(int i = 0; i < p.SubItems.length; i++)
   	   	    	{   
   	   	    	    if(p.SubItems[i].no == no && !isFunction)
   	   	    	        return p.SubItems[i];
   	   	    	    if(p.SubItems[i].noFunction == no && isFunction)
   	   	    	        return p.SubItems[i];
   	   	    		queue.enq(p.SubItems[i]);
   	   	    	}
   	   	    }
   	   	    queue.deq();
   	   }
   	   return null;   	    
   }	
	
}