search.java

完成了α-β剪枝的功能

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
//主类，实现文件的读入与剪枝算法
public class Search{
	public static void main(String args[]){
		try{
			BufferedReader reader;
			FileInputStream fi;
			StringBuffer sb=new StringBuffer();
			int p=0;
			while((p=System.in.read())!=13){//从命令行读入文件名，暂存在一个字符串缓冲区，结束条件为读入回车
				sb.append((char)p);
			}
			String name=new String(sb);//由字符串缓冲区中的字符序列新建一个字符串，代表读入的文件名
			fi=new FileInputStream(name);
			reader=new BufferedReader(new InputStreamReader(fi));
			String str;	
			boolean flag=false;//判读是否开始读入最底层结点的值
			int length=0;//记录读入行的字符串长度
			NodeList nl=new NodeList();//存放结点的一个列表
			Node start= new Node();//根结点
			while((str=reader.readLine())!=null){//以行为单位读入
				length=str.length();
				StringBuffer ss=new StringBuffer(str);
				StringBuffer sa=new StringBuffer("");
				if(str.equals("VALUE")){//当读入的行为VALUE时，标记置为true，表示下一行开始读入最底层结点的值
					flag=true;
					continue;
				}
				if(str.equals("END")){//当读入行为END时，表示所有数据读入完毕，退出循环
					break;
				}
				if(flag){//若当期行开始是最底层结点的值
					StringBuffer s2=new StringBuffer("");
					int num=0;
A:					for(int i=0;i<length;i++){
						if(ss.charAt(i)!=' '&&ss.charAt(i)!='\t'){
							s2.append(ss.charAt(i));//读入对应结点的名字
						}
						else{
							num=i;
							break A;
						}
					}
					String last=new String(s2);
					boolean judge=false;
					int pos=0;
					StringBuffer val=new StringBuffer("");
					Node temp=new Node();
B:					for(int i=0;i<nl.size;i++){
						if(nl.get(i).name.equals(last)){
							for(int j=num;j<length;j++){
								if(ss.charAt(j)!=' '&&ss.charAt(j)!='\t'){
									val.append(ss.charAt(j));//读入对应结点的值所代表的字符串
								}
							}
							pos=i;
							temp=nl.get(i);
							judge=true;//标记，表示找到结点
							break B;
						}
					}
					if(!judge){//未找到与所给结点名相同的结点，退出程序
						System.err.print("Node not found");
						System.exit(1);
					}
					int value=0;
					if(val.charAt(0)=='-'){//若值为负数
						int l=val.length();
						int count=1;
						for(int i=l-1;i>0;i--){
							value=value+((int)val.charAt(i)-48)*count;
							count=count*10;
						}
						value=-value;
						temp.data=value;
					}
					else{//值为正数
						int l=val.length();
						int count=1;
						for(int i=l-1;i>=0;i--){
							value=value+((int)val.charAt(i)-48)*count;
							count=count*10;
						}
						temp.data=value;//给该结点的data赋值为所读入的值
					}
					nl.replace(pos, temp);
				}
				else{//若不是读入最底层结点的值
					if(ss.charAt(0)=='R'&&ss.charAt(1)=='O'&&ss.charAt(2)=='O'&&ss.charAt(3)=='T'){//若为根结点
C:						for(int i=4;i<length;i++){
							if(ss.charAt(i)!=' '){
								for(int j=i;j<length;j++){
									sa.append(ss.charAt(j));//读入根结点的名字
								}
								break C;
							}
						}
						String temp=new String(sa);
						start.name=temp;
						start.isMax=true;//根结点为极大结点
						nl.add(start);//加入列表
					}
					else{//若不是根结点
						StringBuffer s2=new StringBuffer("");
						int num=0;
D:						for(int i=0;i<length;i++){
							if(ss.charAt(i)!=' '&&ss.charAt(i)!='\t'){
								s2.append(ss.charAt(i));//读入作为父结点的结点名
							}
							else{
								num=i;
								break D;
							}
						}
						String father=new String(s2);
						Node fa=new Node();
						boolean judge=false;
						int pos=0;
E:						for(int i=0;i<nl.size;i++){//从列表中寻找该父结点
							if(nl.get(i).name.equals(father)){
								fa=nl.get(i);
								pos=i;
								judge=true;//标记，表明找到父结点
								break E;
							}
						}
						if(!judge){//若为找到父结点，则程序退出
							System.err.print("The father of the node not found");
							System.exit(1);
						}
						boolean in=false;//标记，判断是否得到子结点名
						for(int i=num;i<length-4;i++){
							StringBuffer son=new StringBuffer("");
							while(ss.charAt(i)!='\t'&&ss.charAt(i)!=' '){
								son.append(ss.charAt(i));//得到子结点名
								i++;
								in=true;
							}
							if(in){//若得到子结点名
								String so=new String(son);
								Node x=new Node(so);
								if(fa.isMax){//若其父结点为极大结点，则其为极小节点
									x.isMax=false;
								}
								else{//否则，其为极大结点
									x.isMax=true;
								}
								x.former=fa;//记录其父结点
								fa.son.add(x);//将其加入到其父结点的子结点列表中
								nl.add(x);//将新结点加入列表
								nl.replace(pos, fa);
								in=false;
							}	
						}
					}
				}
			}
			reader.close();//关闭流
			Search se=new Search();
			se.lookup(start);//开始搜索并剪枝
			//输出最后根结点的情况
			System.out.println("根节点："+start.name);
			System.out.println("倒推值："+start.data);
			System.out.println("应走的步骤："+start.next.name);
		}catch(FileNotFoundException e){//异常处理
			System.out.println("Catch "+e);
		}catch(IOException i){//异常处理
			System.out.println("Catch "+i);
		}
	}
	//搜索及剪枝过程
	public void lookup(Node p){
		if(p.son.size!=0){//若当期结点的子结点个数不为0
			for(int i=0;i<p.son.size;i++){//逐一递归搜索其子结点
				if(p.son.get(i).isCut==false){//若子结点未被剪枝，则搜索该子结点
					lookup(p.son.get(i));
				}
			}
		}
		if(p.former==null){//当到达根结点时
			if(p.son.size!=0){//若存在子结点
				for(int i=0;i<p.son.size;i++){//则寻找与当期根结点的data相同的第一个子结点，将根结点的next赋为该子结点
					if(p.data==p.son.get(i).data){
						p.next=p.son.get(i);
						return;
					}
				}
			}
			return;
		}
		else{//当没到达根结点时
			if(p.former.data==-10000){//若当前结点的父结点未被赋值
				p.former.data=p.data;//将其父结点的值赋为当期结点的值
				Node temp=p.former;
				if(p.former.son.size==1){//若其父结点仅有其一个子结点
					while(temp.son.size==1){//当结点仅包含一个子结点时
						if(temp.former!=null){//若父结点不为空
							if(temp.former.data!=-10000){//如果父结点已有值
								if(temp.former.isMax){//若父结点是极大结点
									if(temp.former.data<temp.data){//取两者值中的最大值给父结点
										temp.former.data=temp.data;	
									}	
								}
								else{//若为极小节点
									if(temp.former.data>temp.data){//取两者中的最小值给父结点
										temp.former.data=temp.data;
									}
								}
							}
							else{//若父结点没有值，则赋值为当期结点的值
								temp.former.data=temp.data;
							}
							temp=temp.former;//继续往前判断
						}
						else{//若父结点为空
							return;//返回
						}
					}
				}
				else{//若当前父结点含有多个子结点
					while(temp.former!=null){//若其父结点不为空
						if(temp.former.data==-10000){//若父结点未赋过值，则继续向祖先结点搜索
							temp=temp.former;
							continue;
						}
						else{//若其父结点赋过值
							if(p.former.isMax){//若当前检查结点的父结点是极大结点
								if(!temp.former.isMax){//且其当前祖先结点是极小节点
									if(p.former.data>=temp.former.data){//若α>=β,则β剪枝
										p.former.cut(p);
										p.former.next=p;
										break;//跳出循环
									}
								}
							}
							else{//若当前检查结点的父结点为极小节点
								if(temp.former.isMax){//且当前祖先结点为极大结点
									if(p.former.data<=temp.former.data){//若β<=α,则α剪枝
										p.former.cut(p);
										p.former.next=p;
										break;//跳出循环
									}
								}
							}
						}
						temp=temp.former;//继续往前搜索
					}
				}
			}
			else{//若当前结点的父结点已经被赋值
				Node temp=p.former;
				if(p.former.isMax){//若父结点为极大结点
					if(p.former.data<p.data){//赋为两者中的最大值
						p.former.data=p.data;
					}	
				}
				else{//若父结点为极小节点
					if(p.former.data>p.data){//赋为两者中的最小值
						p.former.data=p.data;
					}
				}
				while(temp.former!=null){//当祖先结点不为空时
					if(temp.former.data==-10000){//若祖先结点未被赋值，则继续往前搜索
						temp=temp.former;
						continue;
					}
					else{//若祖先结点有值
						if(p.former.isMax){//当前结点的父结点为极大结点
							if(!temp.former.isMax){//且当前祖先结点为极小节点
								if(p.former.data>=temp.former.data){//若α>=β则β剪枝
									p.former.cut(p);
									p.former.next=p;
									break;//跳出循环
								}	
							}
						}
						else{//当前结点的父结点为极小节点
							if(temp.former.isMax){//且当前祖先结点为极大结点
								if(p.former.data<=temp.former.data){//若β<=α则α剪枝
									p.former.cut(p);
									p.former.next=p;
									break;//跳出循环
								}
							}
						}
					}
					temp=temp.former;//继续往前搜索
				}
				return;//返回
			}
		}
	}
}