#include<stdio.h>  
#include <ctype.h>  
#define  ok   1  
#define  error 0  
#define  MAXREGLUARLONG 40  
#define  MAXSTATELONG  40      
#define  MAXCAHRSLONG   40    
typedef  int state;  
int iCurrentState=0;   //初态以1开始  
int iPreState=0;  
int iLastForkState=0;  
int iForkState=0;  
int iMaxState=0;  
char cRegluarSting[MAXREGLUARLONG];       //输入的正规式字符串  
char cCharSet[MAXCAHRSLONG];              //字符集  
int  iStateMatrix[MAXSTATELONG][MAXCAHRSLONG];  //状态转换矩阵  
state vStoreRegluarSting()//把字符串读入一个缓冲区中  
{  
    scanf("%s",cRegluarSting);  
    return ok;  
}  
state vPreProcessRegluarSting()  
//对字符串进行预处理,去掉字符串里面的对分析不产生影响  
{  
    int i=0;  
    while(cRegluarSting[i]!=‘\0‘)  
    {  
        if(cRegluarSting[i]==‘*‘)  
        {  
            int j=i+1;  
            while(cRegluarSting[j-1]!=‘\0‘)  
            {   
                cRegluarSting[j-1]=cRegluarSting[j++];      
            }  
        }  
        i++;  
    }  
    return ok;  
}  
void vConstructStateMatrix(char cChar,int istate)//构造状态转换矩阵  
{  
    int i;  
    for(i=0;cCharSet[i]!=‘\0‘;i++)  
        if(cChar==cCharSet[i])  
            break;  
    cCharSet[i]=cChar;  
    iStateMatrix[iPreState][i]=istate;  
}  
void vAanalyseRegluarSting()//对字符串进行从左到右的分析与处理  
{  
    int i=0;  
    for(i=0;cRegluarSting[i]!=0;i++)  
    {  
        if(cRegluarSting[i]==‘(‘)  //NFA出现开始分叉情况  
        {  
            int iTheFirstl=0;  
            int iCharNumBeforl=0;  
            iForkState=iCurrentState;  
            while(cRegluarSting[i]!=‘)‘)  
            {      
                i++;  
                if(isalpha(cRegluarSting[i]))  
                {  
                    if(cRegluarSting[i+1]==‘)‘)  
                        iCurrentState=iLastForkState;  
                    else
                    iCurrentState++;  
                    iCharNumBeforl++;                    vConstructStateMatrix(cRegluarSting[i],iCurrentState);  
                    iPreState=iCurrentState;  
                    if(iCurrentState>iMaxState)  
                        iMaxState=iCurrentState;  
                }  
                if(cRegluarSting[i]==‘|‘)  
                    {  
                        iPreState=iForkState;  
                        if(iTheFirstl==0)  
                        {  
                            iLastForkState=iCurrentState;      
                            iTheFirstl++;  
                        }  
                        if(iCharNumBeforl==1&&cRegluarSting[i+2]==‘|‘)  
                            iCurrentState=iForkState;  
                        iCharNumBeforl=0;  
                    }  
                if(cRegluarSting[i]==‘)‘)  
                {  
                    iPreState=iForkState=iLastForkState;  
                    iCurrentState=iMaxState;  
                }  
            }  
        }  
        else
            {      
                if(isalpha(cRegluarSting[i]))  
                    {  
                        iCurrentState++;                        vConstructStateMatrix(cRegluarSting[i],iCurrentState);  
                        iPreState=iCurrentState;  
                        if(iCurrentState>iMaxState)  
                            iMaxState=iCurrentState;  
                    }  
            }              
    }  
}  
void  vPrintfStateProjectFunction()  
{      
    int icCharSetPointer;  
    int iPreStatePointer;  
    for
(iPreStatePointer=0;iPreStatePointer<MAXSTATELONG;iPreStatePointer++)   
    for(icCharSetPointer=0;icCharSetPointer<MAXSTATELONG;icCharSetPointer++)  
           if(iStateMatrix[iPreStatePointer][icCharSetPointer]>0)       printf("&(%d,%c)=%d\n",iPreStatePointer,cCharSet[icCharSetPointer],iStateMatrix[iPreStatePointer][icCharSetPointer]);      
}  
void vPrintfNfa()//输出NFA  
{  
    int iStateNumble;  
    int i=0;  
    printf("NFA的形式为:(S,$,&,S0,F)\n\n以下为NFA的具体集合内容:\n\n");  
    printf("字符集$为:{");  
    while(cCharSet[i]!=0)  
        if(cCharSet[i+1]==0)  
            printf("%c",cCharSet[i++]);  
        else
            printf("%c,",cCharSet[i++]);  
    printf("}\n");  
    printf("\n状态集S为:{");  
    for (i=0;i<=iMaxState;i++) {  
        if(i==iMaxState)  
            printf("%d",i);  
        else
            printf("%d,",i);  
    }  
    printf("}\n\n");  
    vPrintfStateProjectFunction();  
    printf("\n初态集S0为:{0}\n\n");  
    printf("终态集F为:{%d}",iMaxState);  
}  
void main()  
{  
    vStoreRegluarSting();  
    vPreProcessRegluarSting();  
    vAanalyseRegluarSting();  
    vPrintfNfa();     
}