zidongji.cpp

编译原理中的ＮＦＡ转换到ＤＦＡ（自动机的转换）

#include<stdio.h>
#include<iostream.h>
#include<string.h>


typedef struct node
{
   char a[10];
}T;

typedef struct N
{
   T Node[10];
}NODE;

 struct entry
{
   NODE graph[10];
};

void initize_node(struct N * p,int &x)
{
   
  for(int i=0;i<x;i++)
	  cin>>(p->Node[i]).a;
}

void show_N(struct N * p,int &x)
{
  for(int i=0;i<x;i++)
	  cout<<(p->Node[i]).a;
}

void main()
{
   int line,charn,charnn,i=0;
   char Z[10];
   cout<<"请输入接受字符的个数charn："<<endl;
   cin>>charn;
   charnn=charn+1;
   cout<<"请输入接受的字符："<<endl;
   cin>>Z;
   cout<<"请输入行数line："<<endl;
   cin>>line;
   struct entry GRAPH1,GRAPH2;

/*初始化NFA*/
   struct N *p1=GRAPH1.graph;
   struct N * goal;
   cout<<"请输入起始状态,终止状态："<<endl;
   while(Z[i++]!='\0')
   cout<<"  "<<Z[i-1];
   cout<<endl;
   for(int j=0;j<line;j++)
   {
       initize_node( p1,charnn);
	   p1++; 
   }
   p1=GRAPH1.graph;
   strcpy(GRAPH2.graph[0].Node[0].a,GRAPH1.graph[0].Node[0].a);
   struct N *p2=GRAPH2.graph;
   goal=p2;

//函数声明
   int checkchar(char ch[], struct N  *t, struct N *g);
   void bubblesort(char a[]);
   bool is(char &ch,char t[]);
   void equal(char array[]);
   struct N  * search(char &ch, struct N *s,int &lin);
   void NFA_to_DFA( struct N *N, struct N  *D, struct N  *go,int &line,int &cha);
   void print1( struct N  *x);
   void print2(char &c);
   void print3(char ch[]);
   void show_DFA0( struct N  *d,int &n,char ar[],int &o);
   void show_DFA1( struct N  *d,int &n,char ar[],int &m);
   cout<<"转化的过程中："<<endl;
   i=0;
   while(Z[i++]!='\0')
   cout<<"          "<<Z[i-1];
   cout<<endl;
   NFA_to_DFA(GRAPH1.graph,GRAPH2.graph,goal,line,charnn);
}


 struct N  * search( char &ch,struct N *s,int &lin)
{
   struct N  * temp=s;
   int t=0;
   for(int i=0;i<lin;i++)
  
	  if(ch==temp->Node[0].a[0])
		  break;
	  else
		  temp++;
   return temp;
}

int is(char &ch,char t[])
{
   int i=0,flag=1;
   while(t[i++]!='\0')
	   if(t[i-1]==ch)
		   flag=0;
   return flag;

}
void equal(char array[])
{
	char temp[10]={"\0"};
   int i=0,j=0;
   while(array[i++]!='\0')
   {if(is(array[i-1],temp))
      temp[j++]=array[i-1];
   else
	   i++;
   }
   strcpy(array,temp);
 
}
void bubblesort(char a[])
{
	int l=strlen(a);
	char temp;
	for(int j=1;j<=l-1;j++)
	  for(int i=0;i<l-j;i++)
			if(a[i]>a[i+1])
			{
			   temp=a[i];
			   a[i]=a[i+1];
			   a[i+1]=temp;
			}

}

int  checkchar(char ch[], struct N  *t, struct N  *g)
{
   int flag=1,x=0;
   while(t<=g)
	 if(!strcmp(ch,t->Node[0].a))
	 {
		flag=0;
	   	break;
	 }
	   else t++;
	return flag;
}

void a(char ch[])
{  
   int l=strlen(ch),i=0,j;
   while(ch[i++]!='\0')
	   if(ch[i-1]=='#')
	   {
		   for(j=i;j<=l;j++)
		     ch[j-1]=ch[j];
		   l--;
	   }	   
		 
   ch[l]='\0';

}


void NFA_to_DFA(struct N *N,struct N *D,struct N*go,int &lie,int &cha)
{  
  int x=1,l,y=0,couter=1;
   struct N *temp=0;
   char sym[100]="\0";
   while(x<9)
   { 
    	x++;
	    cout<<D->Node[0].a<<"       ";
        for(int i=1;i<=cha-1;i++)
		{
          if(couter>2)
		  {
			  couter=1;
		      y=0;
		  }
          for(int j=0;j<strlen(D->Node[0].a);j++)
		  {
		   temp=search((D->Node[0].a)[j],N,lie);
           strcat(sym,temp->Node[i].a);
		   equal(sym);
		   bubblesort(sym);
		  }
    	  if(strlen(sym)==1&&!strcmp(sym,"#"))
		  {
		    strcpy(D->Node[i].a,sym);
            l=strlen(D->Node[y].a);
			for(int u=0;u<4-l;u++)
				cout<<" ";
		    cout<<sym;
		  }
	      else
		  {  
            a(sym);
	        strcpy(D->Node[i].a,sym);
			l=strlen(D->Node[y].a);
			for(int u=0;u<4-l;u++)
				cout<<" ";
			cout<<sym<<"    ";
		    if(checkchar(sym,D,go))
			{
	          go++;
		      strcpy(go->Node[0].a,sym);
			}
            sym[0]='\0'; 
		  }
		  couter++;
		  y++;
	
   
		}
     
      cout<<endl;
      D++;
	  sym[0]='\0'; 
   }
}


void print1(struct N  *x)
{
    cout<<"M( "<<x->Node[0].a<<",";
}


void print2(char &c)
{
    cout<<c<<" )"<<"="<<"{";
}


void print3(char ch[])
{
    cout<<ch<<" }"<<endl;
}


void show_DFA0(struct N  *d,int n,char ar[],int &o)
{
   cout<<"DFA:"<<endl;
   int sa=0;
   for(int i=1;i<=n;i++)
   {
       print1(d);
	   print2(ar[o]);
	   print3(d->Node[i].a);
	   d++;
   }
   
}		   
		   
void show_DFA1(struct N  *d,int &n,char ar[],int &m)		   
{
   cout<<"转化后的NFA为："<<endl;
   for(int i=0;i<m;i++)
   {
	   show_DFA0(d,n,ar,i);
	   cout<<endl;
   }
}