p6.cpp

扫描样本字符串

					l1.push_back(val);
					break;
				}
			}//if
			l2.push_back(r[i]);//保存操作符
		}
		else if(r[i]=='*')//遇到'*'
		{
			if(!l2.empty())
			{
				ch=l2.back();
				switch(ch)//向左运算级高,先运算左边的表达式
				{
				case '*':
					ch=l2.back();
					l2.pop_back();
					val1=l1.back();
					l1.pop_back();
					val=AddRepeat(NFAlist,val1,StateNum);
					l1.push_back(val);
					break;
				}
			}//if
			l2.push_back(r[i]);//保存操作符
		}//else if
		i++;
	}//while
	while(!l2.empty())//剩余在'()'外的表达式的运算
	{
		ch=l2.back();
		l2.pop_back();
		switch(ch)
		{
		case '*':
			val1=l1.back();
			l1.pop_back();
			val=AddRepeat(NFAlist,val1,StateNum);
			l1.push_back(val);
			break;
		case '&':
			val2=l1.back();
			l1.pop_back();
			val1=l1.back();
			l1.pop_back();
			val=AddAnd(NFAlist,val1,val2);
			l1.push_back(val);
			break;
		case '|':
			val2=l1.back();
			l1.pop_back();
			val1=l1.back();
			l1.pop_back();
			val=AddOr(NFAlist,val1,val2,StateNum);
			l1.push_back(val);
			break;
		}
	}
	objNFA=val;//保存最终的NFA的始态和终态
}

bool BuildNFA(CString& r)//创建NFA
{
    //NFA_LIST NFAlist;
	Translate(r);
	GetLetters(r);
	RToNFA(r,NFAlist);
	TranslateNFA(NFAlist);

	NFAlist.clear();
	return true;
}

void ClearDFA()
{
	if(DFAtransArray!=NULL)
	{
		delete []DFAtransArray;
		DFAtransArray=NULL;
	}
	if(DFAStateArray!=NULL)
	{
		delete []DFAStateArray;
		DFAStateArray=NULL;
	}
	startlist.clear();
	acceptlist.clear();
}

bool compare(STATE_LIST& T1,STATE_LIST& T2)//比较两个状态集
{
	bool flag=1;
	STATE_LIST::iterator iter1,iter2;
	if(T1.size()!=T2.size())//如果两个状态集的状态数相同do
	{
		flag=0;
		return flag;
	}
	for(iter1=T1.begin(),iter2=T2.begin();iter1!=T1.end();iter1++,iter2++)
	{//逐个状态比较
		if(*iter1!=*iter2)//如果有不同返回false
		{
			flag=0;
		    return flag;
		}
	}
	return flag;//如果没有不同的返回true
}

bool FindStateList(TRANS_LIST& DFAtranslist,STATE_LIST& T)//查找此状态集是否存在于DStates中
{
	bool flag=0;
	TRANS_LIST::iterator iter;
	for(iter=DFAtranslist.begin();iter!=DFAtranslist.end();iter++)
	{
		if(compare(T,iter->dstate))
		{
			flag=1;
			break;
		}
	}
	return flag;
}

bool DFAFindState(STATE_LIST& T,State state)//在状态集T中查找状态state
{
	bool flag=0;
	STATE_LIST::iterator iter;
	for(iter=T.begin();iter!=T.end();iter++)
	{
		if(*iter==state)//如果找到返回true,否则返回false
		{
			flag=1;
			break;
		}
	}
	return flag;
}

/*求出状态集T经过若干空字符转换所到达的状态集n_T*/
void Null_closure(NODE_LIST* NFA_List,STATE_LIST& T,STATE_LIST& n_T)
{
	stack<State> s;//申请一个临时栈,采用深度优先的算法
    STATE_LIST::iterator iter;
	NODE_LIST::iterator iter1;
	State state;
    for(iter=T.begin();iter!=T.end();iter++)//初始状态进栈
	{
		s.push(*iter);
		n_T.push_back(*iter);
	}
	while(!s.empty())//如果栈非空
	{
		state=s.top();//出栈
		s.pop();
		for(iter1=NFA_List[state].begin();iter1!=NFA_List[state].end();iter1++)
		{
			if(iter1->symbol=='\0')//如果是控制符'\0'
			{
				if(!DFAFindState(n_T,iter1->state))//如果还没加进n_T状态集
				{
					n_T.push_back(iter1->state);//加入n_T状态集
					s.push(iter1->state);//把此状态进栈,以便后来再次查找
				}//if
			}//if
		}//for
	}//while
}


/*求出状态集T经过一个字符r转换所到达的状态集r_T*/
void Move(NODE_LIST* NFA_List,char r,STATE_LIST& T,STATE_LIST& r_T)
{
    STATE_LIST::iterator iter;
	NODE_LIST::iterator iter1;
	for(iter=T.begin();iter!=T.end();iter++)//查找整个NFA的邻接表头
	{
		for(iter1=NFA_List[*iter].begin();iter1!=NFA_List[*iter].end();iter1++)
		{
			if(iter1->symbol==r)//如果转换字符为r
			{
				if(!DFAFindState(r_T,iter1->state))//如果还没加进n_T状态集
				{
					r_T.push_back(iter1->state);//加入n_T状态集
				}//if
			}//if
		}//for
	}
}

//用子集构造法创建DFA
void NFAToDFA(NODE_LIST* NFA_List,TRANS_LIST& DFAtranslist)
{
	StateListNode sln;
	TRANS_LIST::iterator curiter;
	LETTER_LIST::iterator iter;
	TransListNode translistnode;
	STATE_LIST T,n_T,r_T;

	T.push_back(objNFA.start);//初始化状态集为NFA状态
	Null_closure(NFA_List,T,n_T);//求出开始状态的经过空字符所到达的状态集,
	//以作为DFA转换表的开始状态集
	n_T.sort();//把n_T排序
    translistnode.dstate=n_T;
    DFAtranslist.push_back(translistnode);//加进转换表
	curiter=DFAtranslist.begin();//curiter把未标志和已标志状态集分开,
	//curiter已标志状态集的最后一个元素,其后后面的状态集全部为未标志的,
	//同时指向的也是转换表中正在添加状态集的表项
	n_T.clear();//n_T清空以便后来使用

	while(curiter!=DFAtranslist.end())//如果还存在未标志的状态表
	{
		T=curiter->dstate;//将当前curiter指向的状态集付给T
		for(iter=letterlist.begin();iter!=letterlist.end();iter++)//for整个字母表
		{
			Move(NFA_List,*iter,T,r_T);//查找T中状态经过字符(*iter)所到达的状态集r_T
			if(r_T.empty())//如果r_T为空,继续查找下一字母的情况
			{
				continue;
			}
			Null_closure(NFA_List,r_T,n_T);//求出状态集r_T经过若干空字符转换所到达的状态集n_T
			n_T.sort();//把状态集n_T的状态排序,以便后来比较状态集
			if(!FindStateList(DFAtranslist,n_T))//如果状态集n_T还没加进DStates中do
			{
				translistnode.dstate=n_T;
				DFAtranslist.push_back(translistnode);//加进DStates
			}
			sln.statelist=n_T;
			sln.symbol=*iter;
            curiter->slnList.push_back(sln);//将n_T及所经过的字符加进转换表
			n_T.clear();//n_T清空以便后来使用
			r_T.clear();//r_T清空以便后来使用
		}
		curiter++;//标志当前状态集
	}
}

int GetStateListIndex(STATE_LIST*& DFAStateArray,STATE_LIST& T)
{
	int i;
	for(i=0;i<DFAStateNum;i++)
	{
		if(compare(DFAStateArray[i],T))
		{
			break;
		}
	}
	return i;
}

void TranslateDFA(TRANS_LIST& DFAtranslist,NODE_LIST*& DFAtransArray)
{
	int i;
	Node node;
	TRANS_LIST::iterator iter;
	STATELISTNODE_LIST::iterator iter1;
	DFAStateNum=DFAtranslist.size();
	DFAStateArray=new STATE_LIST[DFAStateNum];
	DFAtransArray=new NODE_LIST[DFAStateNum];
	for(i=0,iter=DFAtranslist.begin();iter!=DFAtranslist.end();iter++,i++)
	{
		DFAStateArray[i]=iter->dstate;
	}
	for(iter=DFAtranslist.begin(),i=0;iter!=DFAtranslist.end();iter++,i++)
	{
		for(iter1=iter->slnList.begin();iter1!=iter->slnList.end();iter1++)
		{
			node.symbol=iter1->symbol;
			node.state=GetStateListIndex(DFAStateArray,iter1->statelist);
            DFAtransArray[i].push_back(node);
		}
	}
	for(i=0;i<DFAStateNum;i++)
	{
		if(DFAFindState(DFAStateArray[i],objNFA.start))
		{
			startlist.push_back(i);
		}
		if(DFAFindState(DFAStateArray[i],objNFA.end))
		{
			acceptlist.push_back(i);
		}
	}
}

void BuildDFA()
{
	TRANS_LIST DFAtranslist;//保存DFA转换表
	NFAToDFA(NFA_List,DFAtranslist);
	TranslateDFA(DFAtranslist,DFAtransArray);
	DFAtranslist.clear();
}

void VerifySample(char *str)
{
   int i=0;
   State curstate;
   NODE_LIST::iterator iter;

   char ch=str[i];
   curstate = startlist.back();
   

   if(ch=='e')
   {   
	   if(DFAFindState(acceptlist,curstate))
		   printf("yes  \n");
	   else
           printf("no  \n");
	   return;
   }

   while(ch!='\0'&& ch!='e')
   {
       for(iter=DFAtransArray[curstate].begin(); iter!=DFAtransArray[curstate].end();iter++)
       {
          if(iter->symbol==ch)
          {
             curstate=iter->state;
			 i++;
             ch=str[i];
             break; 
          }
	   }
   }
   
   if(DFAFindState(acceptlist,curstate))
       printf("yes \n");  
   else  
       printf("no  \n"); 
}

int main(int argc, char* argv[])
{
   /*************  module 1 ********************/ 
   /////////////  read file and seperate the RE and sample lines
   FILE *stream;
   char buffer[800];   //buffer 存储整个文件内容
   int  i, ch, j=0, k;   //j 是buffer 下标， i 是计数器
   char buf_RE[80];   //buf_RE 为正则表达式字符串
   char buf_sample[10][30];
  
   /* Open file to read line from: */
   if( (stream = fopen( "d:\sample.txt", "r" )) == NULL )
      exit( 0 );

   /* Read in first 80 characters and place them in "buffer": */
   ch = fgetc( stream );
   for( i=0; (i < 80 ) && ( feof( stream ) == 0 ); i++ )
   {
      buffer[i] = (char)ch;
      ch = fgetc( stream );
   }
   buffer[i] = '\0';

   memset(buf_sample,0,300);

   //文件切割出表达式来， 第一行为： buf_RE, buf_RE最后一个字符为 '\0'  
   while(buffer[j]!='\n')
   {
	   buf_RE[j]=buffer[j];
       j++;
   }
   buf_RE[j]= '\0';


   j++;
   i=0;
   k=0;
   
   while(buffer[j]!='\n'&& buffer[j]!='\0')
   {  
	  
	  buf_sample[i][k]=buffer[j];
      j++;
	  k++;
	  if(buffer[j]=='\n')
	  {
		  buf_sample[i][k]='\0';
		  i++;
		  j++;
		  k=0;
	  }
   }
   
 
   fclose(stream);

   ///////////////   give RE to a CString
   rExp=buf_RE;
   /*************  module 1 ********************/ 

   /*************  module 2 ********************/ 

   ///////////////   BuildNFA will build up NFA data structures according to the RE.
   //////////////    The NFA data structure include two parts: NFA_list, the state stes; 
   //////////////    and NODE_list, the adjoining edge table list.
   //////////////    Finally they are united into NFA_List, Array of NODE_LIST*.
   /////////////     
   BuildNFA(rExp);

   /*************  module 2 ********************/ 


   /*************  module 3 ********************/ 
   /////////////     BuildDFA use subset construction to seperate labeleds tates and unlabeled 
   /////////////     states in each step. Each step add one unabled state and count its e_closure
   /////////////     set U, and if the e_closure set U is not found in Dstates, then add U in 
   ////////////      Dstates as unlabeled. Finally buildup DFA data structure as two parts
   ////////////      STATE_LIST* DFAStateArray and NODE_LIST* DFAtransArray. Also startlist
   ///////////       and acceptlist is build up by considering if the old start or accept NFA state 
   ///////////       bcan be found in the new DFA states.
   BuildDFA();

   /*************  module 3 ********************/ 
   
   /*************  module 4 ********************/ 
   ///////////     verify each sample line by DFA data structure. Also considering the empty
   //////////      string situation by check if startlist can be found in acceptlist. 

   i=0;
   while(buf_sample[i][0]!='\0')
   {
	   
	   VerifySample(buf_sample[i]);
	   //printf("%s \n", buf_sample[i]);
	   i++;
	   
   } 
   /*************  module 4 ********************/ 
   
	return 0;
}