q.cpp

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

#include<stdio.h>
#include<string.h>
int shurubiao(int n,char m)
{
	int temp;    
	printf("当当前状态和移进字符分别为%d,%c时请输入转换的状态：",n,m);
	scanf("%d",&temp);
	printf("\n");
	return temp;
}
int biaohao(char a[],char b)
{
	int i,j,k=0;
	j=strlen(a);
	for(;k<j;k++)
	{
		if(a[k]==b)
		{
			i=k;
		}
	}
	return i;
}
void main()
{
	int n,m,z,l,k,p,i,j,o,r,t,g,s=0,h, action,top=0;	
	int yijinguiyuebiao[20][20];
	char guiyueshi[20][20];
    int zhuanhuanhouzhuangtaibiao[20][20];
    int zhuangtaizhan[20];
	char ACTION[20];
	char GOTO[20];
	char zifuchuan[50];
	char fuhaozhan[20];        
    char temp;
         printf("请按表顺序输入终结符和结束符：");
	gets(ACTION);
	puts(ACTION);
        printf("\n");
	printf("请按表顺序输入非终结符：");
	gets(GOTO);
	puts(GOTO);
	z=strlen(ACTION);
	k=strlen(GOTO);	
        printf("\n");
    printf("请输入状态的个数:\n");
		scanf("%d",&g);	
    m=0;
    printf("请按提示输入状态转换，状态请用数字表示，如果是归约状态请加100，如果是接受状态请用字符0来表示，无状态转换时请用-1来表示：\n");
	while(m<g)
	{	
		for(l=0;l<z;l++)
		{		
		    yijinguiyuebiao[m][l]=shurubiao(m,ACTION[l]);                      
		}
		for(p=0;p<k;p++)
		{			
		    zhuanhuanhouzhuangtaibiao[m][p]=shurubiao(m,GOTO[p]);                       
		}
        m++;
	}
	
	printf("请输入归约式的个数：\n");
	scanf("%d",&n);
        printf("请输入归约式！\n");
        for(m=0;m<n; )
            {
                printf("第%d个归约式是：\n",m);
                gets(guiyueshi[m]);
                m++;
             }	
	printf("请输入你所要分析的字符串：\n");
	gets(zifuchuan);
	z=strlen(zifuchuan);
	r=strlen(GOTO);
	t=strlen(ACTION);
    zhuangtaizhan[0]=0;
	fuhaozhan[0]='#';    
	for(m=0; ;m++)
	{
		if(s!=z)
		{
			i=biaohao(ACTION,zifuchuan[s]);
		}
		else i=z-1;
		action=yijinguiyuebiao[zhuangtaizhan[top]][i];
		j=action/100;
		printf("j=%d\n",j);
		action=action%100;
		printf("action=%d\n",action);
		if(action==0||action==-1)
		{
			break;
		}
		else if(j==0)
		{
			printf("经分析后可移进!\n");			
			top++;
			zhuangtaizhan[top]=action;
			printf("移进的状态为%d\n",zhuangtaizhan[top]);
			fuhaozhan[top]=zifuchuan[s];
			printf("移进的字符为%c\n",fuhaozhan[top]);
			s++;
		}
		else if(j==1)
		{
			printf("经分析后可归约!\n"); 
			h=strlen(guiyueshi[action])-1;
			for( o=h;o>0;o--)
			{
				zhuangtaizhan[top]=NULL;
				fuhaozhan[top]=NULL;
				top--;
			}
			printf("top=%d\n",top);
            temp=guiyueshi[action][0];			    
            o=biaohao(GOTO,temp);
            action=zhuanhuanhouzhuangtaibiao[zhuangtaizhan[top]][o];
            top++;
            zhuangtaizhan[top]=action;
			printf("归约后移进的状态为%d\n",zhuangtaizhan[top]);
			fuhaozhan[top]=temp;
			printf("归约后移进的字符为%c\n",fuhaozhan[top]);
		}
											
	}
                           
	if(action==0)
		printf("分析成功！");
	else 
		printf("分析失败！");
}