awa.cpp

判定输入串是不是确定的有穷自动机

#include<stdio.h>
#include<string.h>
int GOTO(int action,char zifu)
{
	if((action==0)&&(zifu=='E'))
		action=1;
	else 
		if((action==2)&&(zifu=='A'))
			 action=6;
		else 
			if((action==3)&&(zifu=='B'))
				 action=7;
			 else 
				if((action==4)&&(zifu=='A'))
					 action=8;
				else 
				    if((action==5)&&(zifu=='B'))
						action=9;
					 else 
						action=-1;
		return action;
}
int ACTION2(int action)
{
  if(action==6)
    action=1;
  else 
	  if(action==7)
         action =2;
        else 
			if(action==8)
                action=3;
             else 
				 if(action==9)
                     action=5;
                  else  
					  if(action==10)
                         action=4;
                        else 
							if(action==11)
                               action=6 ;
   return action;
}
int ACTION1 (int action, char zifu)
{
   if(action==0)
      {
         if(zifu=='a')
            action=2;
         else 
			 if(zifu=='b')   
                 action=3;
             else 
				   action=-1; 
       }
    else 
		if(action==1&&zifu=='#')
			action=1;
	else 
		if(action==2)
            {
              if(zifu=='c')
                 action=4;
              else 
				  if(zifu=='d')
                       action=10;
                  else  
					  action=-1;
             }
     else if(action==3)
           {
              if(zifu=='c')
                action=5;
              else 
				  if(zifu=='d')
                      action=11;
                   else 
						action=-1;
            }
     else if(action==4)
           {
             if(zifu=='c')
                action=4;
             else 
				 if(zifu=='d')
                     action=10;
                 else  
					 action=-1;
           } 
     else  if(action==5)
           {
              if(zifu=='c')
                 action=5;
              else 
				  if(zifu=='d') 
                      action=11;
                  else 
					  action=-1;
           }
           return action;
 
}
void main()
{
  int n,k,l=0;
  int actionstack[20];
  int top=0,action=0,p;
  char Sentence[100],temp;
  char GuiYueShi[7][20];
  char zifustack[20];
  actionstack[0]=0;
  zifustack[0]='#';
  for(n=0;n<7;n++)
	 {
	  printf("请输入产生式%d:\n",n);
	  gets(GuiYueShi[n]);
  }
  printf( "请输入你所要分析的字符串:" );
  gets( Sentence );
  k=strlen(Sentence);
  printf("k=%d",k);
  for(n=0; ;n++)
    {
           
	  if(actionstack[top]==6||actionstack[top]==7||actionstack[top]==8||actionstack[top]==9||actionstack[top]==10||actionstack[top]==11)
	  {    
		   action=ACTION2(action);
		   printf("action: %d\n",action);
           temp=GuiYueShi[action][0];
		   printf("归约为：%c\n",temp);
           k=strlen(GuiYueShi[action]);
		   printf("k=%d\n",k);
		   top=top-k+1;
		   printf("top: %d\n",top);
		   p=actionstack[top];
		   printf("p: %d\n",p);
           action=GOTO(p,temp);
		   printf("归约后的状态为：%d\n",action);
           top++;
		   printf("top=%d\n",top);
           zifustack[top]=temp;
		   printf("zifustack: %c\n",zifustack[top]);
           actionstack[top]=action;
		   printf("actionstack: %d\n",actionstack[top]);
           continue;
	  }
       else if(actionstack[top]==0||actionstack[top]==1||actionstack[top]==2||actionstack[top]==3||actionstack[top]==4||actionstack[top]==5)
		     {
		       l++;
		       action=ACTION1(actionstack[top], Sentence[n]);
			   printf("action=%d",action);
			   if(action==1)break;
               top++;
			   printf("top=%d",top);
               actionstack[top]=action;
               zifustack[top]=Sentence[n];
			   printf("第%d次移进的状态为：%d\n",l,actionstack[top]);
			   printf("第%d次移进的字符为：%c\n",l,zifustack[top]);
	   }
             if( action==-1 )break;
     }
  if( action==1 )
     printf("分析成功！");
  else 
	  printf("分析失败！");
}