nndd.cpp

实现NFA到DFA的转换过程。文件中包含输入格式 见txt 文档

#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include"ARRAY.h"
using namespace std;
static int namenumber=-1;
class DFA;
static int number=0;
class NFAedge
{
public:
  
  NFAedge(int f=-1, char l='#',int t=-1 )
  {
	  from=f;letter=l;to=t;number++;
  }
  
  int from;
  char letter;
  int to; 
  bool operator==(NFAedge & e)
  {
   if(from==e.from&&letter==e.letter &&to==e.to)
	   return true;
   else
	   return false;
  }
  bool operator!=(NFAedge & e)
  {
   if(from!=e.from||letter!=e.letter ||to!=e.to)
	   return true;
   else
	   return false;
  }
  friend ostream & operator<<(ostream &out,const NFAedge& e)
  {
	  out<<e.from<<" "<<e.letter<<" "<<e.to<<endl;
	  return out;
  }
  friend istream & operator>>(istream & in , NFAedge& e)
  {
     in>>e.from>>e.letter>>e.to;
	  return in;
  }
};

class NFA
{
public:
 void input(); 
 void output();
 void Find( int f,Array<NFAedge> &find);
 void Eclosure( int i,Array<int>& result);
 void Eclosure2(Array<int>& f,Array<int>& result);
 void MoveTo(Array<int> &f,char l,Array<int> & to);
 void EclosureMove(Array<int>&f,char l,Array<int>& result);
 //int *E-closure()
private:
 Array<NFAedge> NFAedges ;
 Array<char> Zimubiao;
 int letterCount;
 int startstate;
 int endstate;
 int total;
 friend class DFA;
};

void NFA::Find(int f,Array<NFAedge> &find)
{
	for(int i=0;i<total;i++)
	 if(NFAedges[i].from ==f)
	 {
		find.Add(NFAedges[i]);
	  
	 }
	 
}
void NFA::Eclosure(int i,Array<int> & result)
{
	Array<NFAedge>findresult;
	Find(i,findresult);
	result.Add (i);
	stack<int> temp;
	temp.push(i);
    for(int i=0;i<findresult.Size() ;i++)
		if(findresult[i].letter=='#')
		{
			temp.push(findresult[i].to);
			result.Add (findresult[i].to);
		}
  while(!temp.empty ())
  { 
	  int key;
      key=temp.top ();
	  temp.pop ();
	  findresult.Clear();
	  Find(key,findresult);
	  for(int i=0;i<findresult.Size() ;i++)
		if(findresult[i].letter=='#'&&!result.Have(findresult[i].to))
		{
			temp.push(findresult[i].to);
			result.Add (findresult[i].to);
		}

  }
 
}
void NFA::Eclosure2(Array<int>& f,Array<int>& result)
{
 for(int i=0;i<f.Size ();i++)
	 Eclosure(f[i],result);
}
void NFA::MoveTo(Array<int> &f,char l,Array<int> & t)
{
    Array<NFAedge> e;
	for(int i=0;i<f.Size ();i++)
	  Find(f[i],e);
   for(int j=0;j<e.Size();j++)
	   if(e[j].letter ==l)
		   t.Add (e[j].to);
}
void NFA::EclosureMove(Array<int>&f,char l,Array<int>& result)
{
	Array<int> middle;
  MoveTo(f,l,middle);
  Eclosure2(middle,result);
}
void NFA::input()
{
	cout<<"输入起始状态和终结状态和状态转换函数的个数"<<endl;
	cin>>startstate>>endstate>>total;
	Array<NFAedge> edges(total);
     
	cout<<"请输入所用到的输入字符个数和相应的字符 #代表空串"<<endl;
     cin>>letterCount;
	 Array<char> zimu(letterCount);
	 for(int i=0;i<letterCount;i++)
	 {
      cin>>zimu[i];
	   
	 }
	cout<<"输入每个结点的相关数据"<<endl;
	for(  int i=0;i<total;i++)
	{
		cin>>edges[i];
	}
	NFAedges=edges;
	Zimubiao=zimu;
}
void NFA::output()
{
    for(int i=0;i<total;i++)
		cout<<NFAedges[i];
	cout<<endl;
}
class DFAedge
{
public:
	DFAedge(char f='#',char l='#',char t='#')
           {Dfrom=f;Dletter=l;Dto=t;}
	char Dfrom;
	char Dletter;
	char Dto;
	 friend istream & operator>>(istream & in , DFAedge& e)
  {
     in>>e.Dfrom>>e.Dletter>>e.Dto;
	  return in;
  }
	 friend ostream & operator<<(ostream &out,const DFAedge& e)
  {
	  out<<e.Dfrom<<" "<<e.Dletter<<" "<<e.Dto<<endl;
	  return out;
  }
	
};
class State
{
public:
	State (){};
	State(Array<int>& array){st=array;}
	void Name();
	bool operator==(State& s);
	Array<int> st;
	char name;
};
bool State::operator ==(State& s)
{
 if(st==s.st )
	 return true;
 else 
	 return false;
}
void State:: Name()
{
	++namenumber;
   name= 'A'+namenumber;
}
class DFA
{
public:
	void NFAtoDFA(NFA & nfa);
    void Doutput();
	void Check(char* test,int size);
	bool check(char* test,int size);
	char Goto(DFAedge &e,char l);
private:
 Array<DFAedge> DFAedges;
 Array<char> DZimubiao;
 int DletterCount;
 char Dstartstate;
 Array<char> Dendstate;
 int Dtotal;
};
char DFA::Goto(DFAedge &e,char l)
{
	e.Dto='#';
  for(int i=0;i<Dtotal;i++)
  {
   if(e.Dfrom ==DFAedges[i].Dfrom &&l==DFAedges[i].Dletter )
   {
	   e.Dto =DFAedges[i].Dto;
       return e.Dto;
   }
  }
   return e.Dto;
  
}
void DFA::Doutput()
{
	cout<<"DFA:"<<endl;
    for(int i=0;i<Dtotal;i++)
		cout<<DFAedges[i];
	cout<<endl;
}

void DFA::NFAtoDFA(NFA & nfa)
{
	DFAedge de; 
    Array<char> end(0);
 DletterCount=nfa.letterCount ;
 DZimubiao=nfa.Zimubiao;
 Array<State> state;
 Array<int> Bibao;
  nfa.Eclosure (nfa.startstate ,Bibao);
  state.Add(State(Bibao));
  state[0].Name();
  Dstartstate=state[0].name;
    int biaoji=0;
  while(biaoji!=state.Size())
  {
	   for(int i=0;i<DletterCount;i++)
		{
			int have;
		  Bibao.Clear ();
	      nfa.EclosureMove(state[biaoji].st,DZimubiao[i],Bibao);
		  have=state.Have(State(Bibao));
	      if(!have)
			{
			 state.Add(State(Bibao));
			 state[state.Size()-1].Name();
			 if(Bibao.Have (nfa.endstate ))
					end.Add( state[state.Size()-1].name);
	        de.Dfrom=state[biaoji].name;
			 de.Dletter =DZimubiao[i];
			 de.Dto=state[state.Size()-1].name;
            DFAedges.Add(de);}
	  else
	      { 
	        de.Dfrom=state[biaoji].name;
			 de.Dletter =DZimubiao[i];
			 de.Dto=state[have-1].name;
            DFAedges.Add(de);
	      }
	       	
	    }
		biaoji++;
  }
  Dtotal=DFAedges.Size ();
  Dendstate=end;
}
bool DFA::check(char*test,int size)
{
	DFAedge e;
	e.Dfrom =Dstartstate;
 for(int i=0;i<size;i++)
     {
	   Goto(e,test[i]);
	   if(e.Dto=='#')
		   return false;
	   e.Dfrom=e.Dto;
	   e.Dto='#';
	 }
   if(Dendstate.Have(e.Dfrom))
	   return true;
   else 
	   return false;
} 


void DFA::Check(char*test,int size)
{
  if(check(test,size))
	  cout<<"正确！"<<endl;
  else
	  cout<<"错误！"<<endl;
}
void main()
{
 NFA nfa;
 DFA dfa;
 nfa.input();
 dfa.NFAtoDFA(nfa);
 cout<<endl;
 dfa.Doutput ();
 cout<<endl;
 char test1[10]={'a','b','c','a','b','a','b','a','b','a'};
 char test2[10]={'a','a','a','b','b','b','a','b','a','b'};
 char test3[10]={'a','a','a','b','b','b','a','b','b','a'};
 dfa.Check (test1,10);
 dfa.Check (test2,10);
 dfa.Check (test3,10);
 cout<<endl;
 cout<<"我是如此的高兴 HAPPY~~ :）"<<endl;
 cout<<endl;
}