remanage.cpp

识别正规式

			if(find(endGather.begin(),endGather.end(),MiniDFA_EDGE[m].end)
				==endGather.end())
				endGather.push_back(MiniDFA_EDGE[m].end);
		}

		for(i=0;i<reachedState.size();i++)
		{
			if(find(startGather.begin(),startGather.end(),reachedState[i])
				==startGather.end()&&
				find(miniEndDFA.begin(),miniEndDFA.end(),reachedState[i])
				==miniEndDFA.end())		
			{
				for(int j=0;j<MiniDFA_EDGE.size();j++)
				{
					if(MiniDFA_EDGE[j].end==reachedState[i])
					{
						DFA_EDGE.erase(MiniDFA_EDGE.begin()+j);
						j--;
					}
				}
				reachedState.erase(reachedState.begin()+i);
				break;
			}
		}
	}
	/*****************************end*******************************/
	
	/******************Update the input char************************/
	for(i=0;i<MiniDFA_EDGE.size();i++)
	{
		if(find(miniDFAInput.begin(),miniDFAInput.end(),MiniDFA_EDGE[i].input)
			==miniDFAInput.end())
			miniDFAInput.push_back(MiniDFA_EDGE[i].input);
	}
	/*****************************end*******************************/

	/****************Update non end state of DFA*******************/
	miniNonEndDFA.clear();
	for(i=0;i<MiniDFA_EDGE.size();i++)
	{
		if(find(miniEndDFA.begin(),miniEndDFA.end(),MiniDFA_EDGE[i].start)
			==miniEndDFA.end()&&
			find(miniNonEndDFA.begin(),miniNonEndDFA.end(),MiniDFA_EDGE[i].start)
			==miniNonEndDFA.end())
			miniNonEndDFA.push_back(MiniDFA_EDGE[i].start);
		if(find(miniEndDFA.begin(),miniEndDFA.end(),MiniDFA_EDGE[i].end)
			==miniEndDFA.end()&&
			find(miniNonEndDFA.begin(),miniNonEndDFA.end(),MiniDFA_EDGE[i].end)
			==miniNonEndDFA.end())
			miniNonEndDFA.push_back(MiniDFA_EDGE[i].end);		
	}
	/*****************************end*******************************/

	/*********************Test***********************/	
	
	/*cout<<"After remove Futility:"<<endl;

	cout<<"Start state:"<<miniStartDFA<<endl;

	cout<<"NonEnd state gather: ";
	for( i=0;i<miniNonEndDFA.size();i++)
		cout<<miniNonEndDFA[i]<<" ";
	cout<<endl;

	cout<<"End state gather: ";
	for(i=0;i<miniEndDFA.size();i++)
		cout<<miniEndDFA[i]<<" ";
	cout<<endl;

	for(i=0;i<MiniDFA_EDGE.size();i++)
	{
		cout<<"Edge "<<i<<": "<<MiniDFA_EDGE[i].start<<"  "
			<<MiniDFA_EDGE[i].input<<"  "
			<<MiniDFA_EDGE[i].end<<"  "<<endl;
	}*/
	/*********************End***********************/
}
int REManage::MovdDFA(int start,char input)
{
	for(int i=0;i<DFA_EDGE.size();i++)
	{
		if(DFA_EDGE[i].start==start
			&&DFA_EDGE[i].input==input)
			return DFA_EDGE[i].end;
	}

	return -1;
}

int REManage::FindGather(int end,vector<vector<int> > gather)
{
	if(end<0)
		return end;
	for(int i=0;i<gather.size();i++)
		if(find(gather[i].begin(),gather[i].end(),end)!=gather[i].end())
			return i;
	return -1;
}

/*合并DFA中的等价状态*/
/*
===================
输入：
	  DFAInput
	  startDFA
	  endDFA
	  nonEndDFA
	  DFA_EDGE
===================
输出：
	  miniStartDFA
	  miniEndDFA
      miniNonEndDFA
	  MiniDFA_EDGE
	  miniStateGather	  
===================
*/
void REManage::CombineEquality()
{
	vector<vector<int> > completeStateGather;
	vector<vector<int> > currentStateGather;

	completeStateGather.clear();
	currentStateGather.clear();

	completeStateGather.push_back(nonEndDFA);
	completeStateGather.push_back(endDFA);
	
	int initSize=completeStateGather.size()-1;
	bool seperate=true;
	
	/*********Beginning of generate the new gather**************/

	for(int allState=0;allState<completeStateGather.size();allState++)
	{
		initSize=completeStateGather.size()-1;

		while(completeStateGather.size()>initSize)
		{
			vector<int> testState=completeStateGather[allState];
			initSize=completeStateGather.size();				
			if(testState.size()==1)
				continue;
			for(int i=0;i<DFAInput.size();i++)
			{	
				seperate=true;
				currentStateGather.clear();
				currentStateGather.resize(completeStateGather.size()+1);

				for(int j=0;j<testState.size();j++)
				{
					int gather=FindGather(
						MovdDFA(testState[j],DFAInput[i]),
						completeStateGather);
					currentStateGather[gather+1].push_back(testState[j]);
				}
				
				for(j=0;j<currentStateGather.size();j++)
				{
					if(currentStateGather[j].size()==testState.size())
					{
						seperate=false;
						break;
					}
				}
				
				if(seperate)
				{
					completeStateGather.erase(completeStateGather.begin()+allState);			
					for(j=0;j<currentStateGather.size();j++)
					{
						if(currentStateGather[j].size()>0)
						{
							completeStateGather.push_back(currentStateGather[j]);
						}
					}
					break;
				}
					
			}
		}	
	}
	sort(completeStateGather.begin(),completeStateGather.end());
	/************************End***************************/

	miniStateGather=completeStateGather;

	/********Generate the edge of the Minimum DFA**********/

	for(int i=0;i<DFA_EDGE.size();i++)
	{
		EDGE temp;
		temp.input=DFA_EDGE[i].input;
		temp.start=completeStateGather[FindGather(DFA_EDGE[i].start,completeStateGather)][0];
		temp.end=completeStateGather[FindGather(DFA_EDGE[i].end,completeStateGather)][0];
		
		if(find(MiniDFA_EDGE.begin(),MiniDFA_EDGE.end(),temp)==MiniDFA_EDGE.end())
			MiniDFA_EDGE.push_back(temp);
	}
	/***************************End************************/
	
	/************Get start state and end state gather of MiniDFA*******/
	for(i=0;i<miniStateGather.size();i++)
	{
		if(find(miniStateGather[i].begin(),miniStateGather[i].end(),startDFA)
			!=miniStateGather[i].end())
			miniStartDFA=miniStateGather[i][0];

		for(int j=0;j<miniStateGather[i].size();j++)
		{
			if(find(endDFA.begin(),endDFA.end(),miniStateGather[i][j])
				!=endDFA.end())
			{
				if(find(miniEndDFA.begin(),miniEndDFA.end(),miniStateGather[i][0])
					==miniEndDFA.end())
					miniEndDFA.push_back(miniStateGather[i][0]);
			}
			else
			{
				if(find(miniNonEndDFA.begin(),miniNonEndDFA.end(),miniStateGather[i][0])
					==miniNonEndDFA.end())
					miniNonEndDFA.push_back(miniStateGather[i][0]);
			}
		}
	}
	/*****************************End******************************/

	/************************Test**************************/
	/*cout<<"=============MiniDFA============="<<endl;
	cout<<"After combine equality:"<<endl;
	for(int j=0;j<miniStateGather.size();j++)
	{
		cout<<"Gather "<<j<<": ";
		for(int m=0;m<miniStateGather[j].size();m++)
			cout<<miniStateGather[j][m]<<" ";
		cout<<endl;
	}

	cout<<"Start state:"<<miniStartDFA<<endl;

	cout<<"End state gather:";
	for(i=0;i<miniEndDFA.size();i++)
		cout<<miniEndDFA[i]<<" ";
	cout<<endl;

	cout<<"NonEnd state gather:";
	for(i=0;i<miniNonEndDFA.size();i++)
		cout<<miniNonEndDFA[i]<<" ";
	cout<<endl;
	
	for(i=0;i<MiniDFA_EDGE.size();i++)
	{
		cout<<"Edge "<<i<<": "<<MiniDFA_EDGE[i].start<<"  "
			<<MiniDFA_EDGE[i].input<<"  "
			<<MiniDFA_EDGE[i].end<<"  "<<endl;
	}*/
	/*************************End**************************/
}

/*最小化DFA*/
void REManage::MinimizeDFA()
{
	this->CombineEquality();
	this->RemoveFutility();
}
void REManage::clear()
{
	NFA_EDGE.clear();
	NFAInput.clear();
	startNFA.clear();
	endNFA.clear();
	
	DFAInput.clear();
	endDFA.clear();
	nonEndDFA.clear();
	DFA_EDGE.clear();
	DFAStateGather.clear();

	miniDFAInput.clear();
	miniEndDFA.clear();
	miniNonEndDFA.clear();
	MiniDFA_EDGE.clear();
    miniStateGather.clear();
}
//设置正规式
void REManage::setRE(string re)
{
	this->state=1;
	this->clear();
	this->re=re;
	this->isREUpdate=true;
}

//设置NFA
void REManage::setNFA(vector<EDGE> edge,vector<int> start,vector<int> end)
{
	//对输入与输出清空
	this->clear();
	this->state=1;
	this->NFA_EDGE=edge;
	this->startNFA=start;
	this->endNFA=end;

	for(int i=0;i<edge.size();i++)
	{
		if(find(NFAInput.begin(),NFAInput.end(),edge[i].input)
			==NFAInput.end())
			NFAInput.push_back(edge[i].input);
	}

	this->isNFAUpdate=true;
}

//设置DFA
void REManage::setDFA(vector<EDGE> edge,int start,vector<int> end)
{
	//对输入与输出清空
	this->clear();
	this->state=1;
	this->DFA_EDGE=edge;
	this->startDFA=start;
	this->endDFA=end;

	for(int i=0;i<edge.size();i++)
	{
		if(find(DFAInput.begin(),DFAInput.end(),edge[i].input)
			==DFAInput.end())
			DFAInput.push_back(edge[i].input);
		if(find(endDFA.begin(),endDFA.end(),edge[i].start)
			==endDFA.end()&&
			find(nonEndDFA.begin(),nonEndDFA.end(),edge[i].start)
			==nonEndDFA.end())
			nonEndDFA.push_back(edge[i].start);
		if(find(endDFA.begin(),endDFA.end(),edge[i].end)
			==endDFA.end()&&
			find(nonEndDFA.begin(),nonEndDFA.end(),edge[i].end)
			==nonEndDFA.end())
			nonEndDFA.push_back(edge[i].end);
	}
	this->isDFAUpdate=true;
}

void REManage::Process()
{
	if(isREUpdate)
	{
		this->ProcessREToNFA();
		this->NFAInput=this->REInput;
		this->DFAInput=this->NFAInput;
		this->ProcessNFAToDFA();
		this->MinimizeDFA();
	}	
	else if(isNFAUpdate)
	{
		this->DFAInput=this->NFAInput;
		this->ProcessNFAToDFA();
		this->MinimizeDFA();
	}
	else if(isDFAUpdate)
	{
		this->MinimizeDFA();
	}

	this->OutputResult();

	HWND note=FindWindow("notepad",NULL);
	::SendMessage(note,WM_CLOSE,0,0);
	ShellExecute(NULL,"open","Result.txt",NULL,NULL,SW_SHOWNORMAL);

	this->isREUpdate=false;
	this->isNFAUpdate=false;
	this->isDFAUpdate=false;
}
void REManage::OutputResult()
{
	out.close();
	out.open("Result.txt");
	out<<"=================Start=================="<<endl;
	out<<endl;
	if(isREUpdate)
	{
		out<<"正规式："<<this->re<<endl;
		out<<"正规式输入符：";
		for(int i=0;i<this->REInput.size();i++)
			out<<this->REInput[i]<<" ";
		out<<endl;

		out<<"==================NFA==================="<<endl;
		out<<"初态集：";
		for(i=0;i<this->startNFA.size();i++)
			out<<this->startNFA[i]<<" ";
		out<<endl;
		out<<"终态集：";
		for(i=0;i<this->endNFA.size();i++)
			out<<this->endNFA[i]<<" ";
		out<<endl;

		out<<"NFA的边集："<<endl;
		for(i=0;i<this->NFA_EDGE.size();i++)
		{
			out<<"Index "<<i<<": ";
			out<<this->NFA_EDGE[i].start<<"  "
				<<this->NFA_EDGE[i].input<<"  "
				<<this->NFA_EDGE[i].end<<endl;
		}

		out<<endl;

		out<<"==================DFA==================="<<endl;
		out<<"初态："<<startDFA<<endl;
		out<<"终态集：";
		for(i=0;i<this->endDFA.size();i++)
			out<<this->endDFA[i]<<" ";
		out<<endl;

		out<<"DFA的边集："<<endl;
		for(i=0;i<this->DFA_EDGE.size();i++)
		{
			out<<"Index "<<i<<": ";
			out<<this->DFA_EDGE[i].start<<"  "
				<<this->DFA_EDGE[i].input<<"  "
				<<this->DFA_EDGE[i].end<<endl;
		}

		out<<endl;

		out<<"==============最小化的DFA==============="<<endl;
		out<<"初态："<<miniStartDFA<<endl;
		out<<"终态集：";
		for(i=0;i<this->miniEndDFA.size();i++)
			out<<this->miniEndDFA[i]<<" ";
		out<<endl;

		out<<"最小化DFA的边集："<<endl;
		for(i=0;i<this->MiniDFA_EDGE.size();i++)
		{
			out<<"Index "<<i<<": ";
			out<<this->MiniDFA_EDGE[i].start<<"  "
				<<this->MiniDFA_EDGE[i].input<<"  "
				<<this->MiniDFA_EDGE[i].end<<endl;
		}

	}	
	else if(isNFAUpdate)
	{
		out<<"==================DFA==================="<<endl;
		out<<"初态："<<startDFA<<endl;
		out<<"终态集：";
		for(int i=0;i<this->endDFA.size();i++)
			out<<this->endDFA[i]<<" ";
		out<<endl;

		out<<"DFA的边集："<<endl;
		for(i=0;i<this->DFA_EDGE.size();i++)
		{
			out<<"Index "<<i<<": ";
			out<<this->DFA_EDGE[i].start<<"  "
				<<this->DFA_EDGE[i].input<<"  "
				<<this->DFA_EDGE[i].end<<endl;
		}
		out<<endl;
		out<<"==============最小化的DFA==============="<<endl;
		out<<"初态："<<miniStartDFA<<endl;
		out<<"终态集：";
		for(i=0;i<this->miniEndDFA.size();i++)
			out<<this->miniEndDFA[i]<<" ";
		out<<endl;

		out<<endl;

		out<<"最小化DFA的边集："<<endl;
		for(i=0;i<this->MiniDFA_EDGE.size();i++)
		{
			out<<"Index "<<i<<": ";
			out<<this->MiniDFA_EDGE[i].start<<"  "
				<<this->MiniDFA_EDGE[i].input<<"  "
				<<this->MiniDFA_EDGE[i].end<<endl;
		}
	}
	else if(isDFAUpdate)
	{
		out<<"==============最小化的DFA==============="<<endl;
		out<<"初态："<<miniStartDFA<<endl;
		out<<"终态集：";
		for(int i=0;i<this->miniEndDFA.size();i++)
			out<<this->miniEndDFA[i]<<" ";
		out<<endl;

		out<<"最小化DFA的边集："<<endl;
		for(i=0;i<this->MiniDFA_EDGE.size();i++)
		{
			out<<"Index "<<i<<": ";
			out<<this->MiniDFA_EDGE[i].start<<"  "
				<<this->MiniDFA_EDGE[i].input<<"  "
				<<this->MiniDFA_EDGE[i].end<<endl;
		}
	}
	out<<endl;
	out<<"==================End==================="<<endl;
}
bool REManage::TestString(string str)
{
	int currentState,nextState;
	nextState=miniStartDFA;
	
	
	for(int i=0;i<str.size();i++)
	{
		currentState=nextState;
		for(int j=0;j<MiniDFA_EDGE.size();j++)
			if(MiniDFA_EDGE[j].start==currentState&&
				MiniDFA_EDGE[j].input==str[i])
			{
				nextState=MiniDFA_EDGE[j].end;
				break;
			}
		if(j==MiniDFA_EDGE.size())
			break;
	}
	if(i=str.size()&&
		find(miniEndDFA.begin(),miniEndDFA.end(),nextState)!=miniEndDFA.end())
		return true;
	else
		return false;
}