compile_work2.cpp

正则表达式转换为有穷自动机的算法

	   Si++;
   }
   else if (statement[Si]==')')
   {
    top--;
	while (stack[top]!='(')
	{
      ReversePolishString[RPSi]=stack[top];
      top--;
      RPSi++;
	}
	Si++;
   }
   else if (statement[Si]=='*')
   {    
	top--;
	while(stack[top]=='*' && top>=0)
	{
      ReversePolishString[RPSi]=stack[top];
      top--;
      RPSi++;
	}
	top++;
	stack[top]=statement[Si];
	Si++;
	top++;
   }
   else if (statement[Si]=='|')
   {
    top--;
	while((stack[top]=='*' || stack[top]== '+' || stack[top]== '|') && top>=0)
	{
      ReversePolishString[RPSi]=stack[top];
      top--;
      RPSi++;
	}
	top++;
	stack[top]=statement[Si];
	Si++;
	top++;
   }
  }
  top--;
  while(top>=0) //将剩余操作符号串接到{0，1}*后边   
  {
   ReversePolishString[RPSi]=stack[top];
   top--;
   RPSi++;
  }
  ReversePolishString[RPSi]='\0';
}
////////////////////    End Regular==>NFA	//////////////////////////////
//////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////
//////////////////   Begin NFA==>DFA  ////////////////////////////////////

int c=0;//全局变量
//temp
void line(int s[],int n)//排序
{
	for(int i=1;i<n;i++)
		for(int j=i;(j>0)&&(s[j]<s[j-1]);j--)
		{
			int temp=s[j];
			s[j]=s[j-1];
			s[j-1]=temp;
		}
}

void out(int s[],int &n)//检查重复
{
	for(int i=0;i<n-1;i++)
		if(s[i]==s[i+1])
		{
			for(int j=i;j<n-1;j++) s[j]=s[j+1];
			n--;
			i--;
		}
}

template <class Elem> class stack
{
	private:
		int size;
		int top;
		Elem *listArray;
	public:
		stack(int sz=100)
		{	size=sz;top=0;listArray=new Elem[sz];}
		~stack()
		{	delete []listArray;}
		bool push(const Elem& item)
		{
			if(top==size) return false;
			else {listArray[top++]=item;return true;}
		}
		bool pop(Elem& it)
		{
			if(top==0) return false;
			else {it=listArray[--top];return true;}
		}
		int length() const {return top;}
};

void closure(int s[][100],int& n,int z[],int n0,int sub[],int& subn)//数组的闭包
{
	stack<int>t;
	int i=0;
	for(int m=0;m<n0;m++)
	{
		t.push(z[m]);
		sub[i++]=z[m];
	}
	int a,mark=0;
	while(t.length())
	{
		t.pop(a);
		for(int j=0;j<n;j++)
			if(s[a][j]==2)
			{
				mark=0;
				for(int k=0;k<i;k++) if(sub[k]==j) mark=1;
				if(mark==0)
				{
					sub[i++]=j;
					t.push(j);
				}
			}
	}
	subn=i;//闭包的个数
	line(sub,i);//排序
}

void closure(int s[][100],int& n,int z,int sub[],int& subn)//初始状态的闭包
{
	stack<int>t;
	int i=0;
	t.push(z);
	sub[i++]=z;
	int a,mark=0;
	while(t.length ())
	{
		t.pop(a);
		for(int j=0;j<n;j++)
			if(s[a][j]==2)
			{
				mark=0;
				for(int k=0;k<i;k++) if(sub[k]==j) mark=1;
				if(mark==0)
				{
					sub[i++]=j;
					t.push(j);
				}
			}
	}
	subn=i;
	line(sub,i);
}

class DFA//DFA中的状态集合
{
	public:
		void add(int S[],int N)
		{
			for(int i=0;i<N;i++) s[i]=S[i];//初始化
			n=N;
			c++;
		}
		int s[100];
		int n;
		int next0;//零的出边
		int next1;//一的出边
};

bool eq(DFA a,DFA b)
{
	if(a.n!=b.n) return false;
	else
	{
		for(int i=0;i<a.n;i++) if(a.s[i]!=b.s[i]) return false;
	}
	return true;
}
	
////////////////////      End NFA==>DFA   	//////////////////////////////
//////////////////////////////////////////////////////////////////////////

void main()
{
    char statement[25], ReversePolishString[25];
    cout<<"请输入正则式( 注意对单个输入有*操作的时候要有$合成，比如求0*，要有($0)* ): "<<endl;
    cin>>statement;
    ToReversePolish(statement,ReversePolishString);
    cout<<ReversePolishString<<endl<<endl;
    ToNFA(ReversePolishString);
	int s[100][100];
	cout<<endl<<"****** NFA=====>DFA ******"<<endl;
	int n=1;
    for(int m=0;m<relationi;m++)  //求nfa中状态数目
	{
		if(n<=relation[m].NextState)   n=relation[m].NextState;
	}
    n=n+1;    
	cout<<"转化后NFA的状态数目："<<n;
	for(int i=0;i<n;i++)   //初始化边
		for(int j=0;j<n;j++) s[i][j]=-1;
    for (i=0;i<relationi;i++)
	{
       int current=relation[i].CurrentState;
       int next  = relation[i].NextState;
       if (relation[i].TransitionElement=='$')
            s[current][next]=2; 
       else if(relation[i].TransitionElement=='0')
	        s[current][next]=0;
       else s[current][next]=1;
	} 

	int Start=0; 
	int *End=new int[1];
	End[0]=n;
	
	int sub[100],subn,tt[100],j,k,l,w=0,sign;
	
	
	closure(s,n,Start,sub,subn);//初始状态的闭包
	
	DFA *dfa=new DFA[100],temp,temp2;//DFA的状态数组以及两个对象
	
	for(i=0;i<100;i++) 
	dfa[i].next0=dfa[i].next1=-1;
	dfa[c].add(sub,subn);// C：全局变量，初始值为零
	
	stack<DFA>t;
	t.push(dfa[0]);//初始状态的闭包入栈
	while(t.length())
	{
		t.pop(temp);
		for(i=0;i<2;i++)
		{
			for(j=0;j<temp.n;j++)//temp.n：DFA状态的数目
				for(k=0;k<n;k++)//对每一个输入的状态进行检查（零或一）
					if(s[(temp.s[j])][k]==i)
					{
						tt[w++]=k;//求MOVE
						continue;
					}
			closure(s,n,tt,w,sub,subn);//对MOVE作闭包
			temp2.add(sub,subn);
			c--;
			for(l=0;!(eq(temp2,dfa[l]))&&(l<c);l++);//DFA数组中检查是否有重复的项
			if(l==c) sign=0;
			else sign=1;
			if(sign==0)
			{
				dfa[c].add(sub,subn);//生成一个新的DFA状态集合
				t.push(dfa[c-1]);//将另一个
			}
			for(int m=0;!(eq(temp,dfa[m]));m++);
			if((i==0)&&(sign==1)) dfa[m].next0=l;
			if((i==1)&&(sign==1)) dfa[m].next1=l;
			if((i==0)&&(sign==0)) dfa[m].next0=c-1;
			if((i==1)&&(sign==0)) dfa[m].next1=c-1;
			w=0;		
		}
	}
    cout<<endl;
//	cout<<"*************************************************************************"<<endl<<endl;
////////
	cout<<"1.状态的集合({}内的为nfa中的状态)："<<endl;
	for(i=0;i<c;i++)
	{
		if(dfa[i].n>0)
        {
		cout<<"DFA状态"<<i<<":"<<"{ ";
		for(j=0;j<dfa[i].n;j++) cout<<dfa[i].s[j]<<" ";
		cout<<"}"<<endl;
		}
	}
	cout<<endl;
////////
	cout<<"2.输入符号集合："<<endl<<"{ 0 1 }"<<endl<<endl;
////////
	cout<<"3.关系："<<endl;
	cout<<"状态\t"<<"输入符号\t"<<endl<<'\t'<<"0\t"<<"1\t"<<endl;
	for(i=0;i<c;i++)
	{
	  if(dfa[i].n>0)
	  {
		cout<<i<<'\t';
		if(dfa[i].next0!=-1) 
          if(dfa[dfa[i].next0].n>0) 
			 cout<<dfa[i].next0<<'\t';
		  else cout<<"—"<<'\t';
		else cout<<"无\t";
		if(dfa[i].next1!=-1)
          if(dfa[dfa[i].next1].n>0)
			 cout<<dfa[i].next1<<endl;
		  else cout<<"—"<<'\t'<<endl;
		else cout<<"无"<<endl;
	  }
	}
	cout<<endl;
///////
	cout<<"4.开始状态："<<endl<<"{ ";
	cout<<Start<<" ";
	cout<<"}"<<endl<<endl;
///////
	cout<<"5.终止状态："<<endl<<"{ ";
	l=0;
	for(i=0;i<c;i++)
	{
		for(j=0;j<dfa[i].n;j++)
		{if(dfa[i].s[j]==End[0]-1)  tt[l++]=i;}
	}	
	line(tt,l);
	out(tt,l);
	for(i=0;i<l;i++) cout<<tt[i]<<" ";
	cout<<"}"<<endl;
///////
}