remanage.cpp

识别正规式

	}

}

/*消除DFA中的无用状态*/
void REManage::RemoveFutility()
/*
===================
输入：
	  miniStartDFA
	  miniEndDFA
      miniNonEndDFA
	  MiniDFA_EDGE
	  miniStateGather
===================
输出：
	  miniStartDFA
	  miniEndDFA
      miniNonEndDFA
	  MiniDFA_EDGE
	  miniStateGather	  
===================
*/
{

	vector<unsigned>	reachedState;
	queue<unsigned>	reached;

	vector<unsigned> startGather;
	vector<unsigned>	endGather;

	reachedState.clear();	


	reached.push(miniStartDFA);
	reachedState.push_back(miniStartDFA);

	while(reached.size()>0)
	{
		unsigned front=reached.front();
		reached.pop();

		for(unsigned i=0;i<MiniDFA_EDGE.size();i++)
		{
			if(find(DFAInput.begin(),DFAInput.end(),MiniDFA_EDGE[i].input)
				==DFAInput.end())
				DFAInput.push_back(MiniDFA_EDGE[i].input);

			if(MiniDFA_EDGE[i].start==front)
			{
				if(find(reachedState.begin(),reachedState.end(),MiniDFA_EDGE[i].end)
					==reachedState.end())
				{
					reachedState.push_back(MiniDFA_EDGE[i].end);
					reached.push(MiniDFA_EDGE[i].end);
				}
			}
		}
	}
	sort(reachedState.begin(),reachedState.end());

	vector<EDGE>::iterator iterEDGE;
	
	for(unsigned i=0;i<MiniDFA_EDGE.size();i++)
	{
		if(find(reachedState.begin(),reachedState.end(),MiniDFA_EDGE[i].start)
			==reachedState.end())
		{
			iterEDGE=MiniDFA_EDGE.begin()+i;
			MiniDFA_EDGE.erase(iterEDGE++);
			i--;
		}
	}

	vector<unsigned>::iterator iterEnd;
	for(unsigned i=0;i<miniEndDFA.size();i++)
	{
		if(find(reachedState.begin(),reachedState.end(),miniEndDFA[i])
			==reachedState.end())
		{
			iterEnd=miniEndDFA.begin()+i;
			miniEndDFA.erase(iterEnd++);
			i--;
		}
	}
	
	size_t initSize=reachedState.size()+1;

	while(reachedState.size()<initSize)
	{
		initSize=reachedState.size();

		startGather.clear();
		endGather.clear();

		for(unsigned m=0;m<MiniDFA_EDGE.size();m++)
		{
			if(find(startGather.begin(),startGather.end(),MiniDFA_EDGE[m].start)
				==startGather.end())
				startGather.push_back(MiniDFA_EDGE[m].start);
			if(find(endGather.begin(),endGather.end(),MiniDFA_EDGE[m].end)
				==endGather.end())
				endGather.push_back(MiniDFA_EDGE[m].end);
		}

		for(unsigned 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(unsigned 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;
			}
		}
	}

	for(unsigned 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);
	}

}
size_t REManage::MovdDFA(unsigned start,char input)
{
	for(unsigned 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;
}

unsigned REManage::FindGather(unsigned end,vector<vector<unsigned> > gather)
{
	if(end<0)
		return end;
	for(unsigned 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<unsigned> > completeStateGather;
	vector<vector<unsigned> > currentStateGather;

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

	completeStateGather.push_back(nonEndDFA);
	completeStateGather.push_back(endDFA);
	
	size_t initSize=completeStateGather.size()-1;
	bool seperate=true;
	

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

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

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

	miniStateGather=completeStateGather;

	for(unsigned 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);
	}
	for(unsigned i=0;i<miniStateGather.size();i++)
	{
		if(find(miniStateGather[i].begin(),miniStateGather[i].end(),startDFA)
			!=miniStateGather[i].end())
			miniStartDFA=miniStateGather[i][0];

		for(unsigned 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]);
			}
		}
	}
}

/*最小化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();
}
//设置正规式
bool REManage::setRE(string re)
{
	this->state=1;
	this->clear();
	this->re=re;
	if(REJudge() == false)return false;
	return true;
}

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

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

}

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

	for(unsigned 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);
	}
}

void REManage::Process()
{
	this->ProcessREToNFA();
	this->NFAInput=this->REInput;
	this->DFAInput=this->NFAInput;
	this->ProcessNFAToDFA();
	this->MinimizeDFA();
	this->OutputResult();
}
void REManage::OutputResult()
{
	cout<<"==================开始==================="<<endl;
	cout<<endl;
	cout<<"正规式："<<this->re<<endl;
	cout<<"正规式输入符：";
	for(unsigned i=0;i<this->REInput.size();i++)
		cout<<this->REInput[i]<<" ";
	cout<<endl;

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

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

	cout<<endl;

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

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

	cout<<endl;

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

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

	cout<<endl;
	cout<<"==================结束==================="<<endl;
}

bool REManage::REJudge()const
{
	int leftbracket = 0,rightbracket = 0;
	for(unsigned i = 0;i < re.length();i++)
	{
		if(re[i] != '.'&&re[i] != '|'
			&&re[i] != '*'&&re[i] != '('
			&&re[i] != ')'&&isalnum(re[i]) == 0)
			return false;										//不能有非法字符
		if((re[i] == '.'||re[i] == '|'
			||re[i] == '*'||re[i] == ')')&&i == 0)
			return false;			//'.''|''*'')'不能是第一个字符
		if((re[i] == '.'||re[i] == '|'||re[i] == '(')&&
			i == re.length()-1)
			return false;				//'.''|''('不能是最后一个字符
		if(re[i] == '.'&&
			(re[i-1] == '|'||re[i+1] == '|'
			||re[i+1] == '.'||re[i-1] == '('
			||re[i+1] == ')'||re[i+1] == '*'))
			return false;								//'.'前后不允许出现的符号
		if(re[i] == '|'&&
			(re[i+1] == '*'||re[i+1] == ')'
			||re[i-1] == '('||re[i+1] == '|'))
			return false;						//'|'前后不允许出现的符号
		if(re[i] == '*'&&(re[i-1] == '('||re[i-1] == '*'))
			return false;							//'*'前后不允许出现的符号
		if(re[i] == ')'&&leftbracket == 0)
			return false;							//式子的括号必须以'('开始
		if(re[i] == '(')leftbracket++;
		if(re[i] == ')')rightbracket++;			//给左右括号计数看是否匹配
	}
	if(leftbracket != rightbracket)return false;	//左右括号数量不匹配
	return true;
}