//RND.h   

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define Max_alphabet 20
#define Max_regexp 50
#define Max_StateTransition 20
#define Max_State 200
#define FileAlphabetPath "alphabet.txt"
#define FileRegexpPath "regexp.txt" 
#define FileOutputPath "Report.txt"


//轉換弧類型定義
typedef struct TRANS
{
    int dest;//目的狀態點
    char sign;//轉換變量
    struct TRANS* next;//指向下一個轉換弧
} Trans;

//狀態類型定義
typedef struct STATE
{
    int id ;    //狀態編號
    int numOfTrans;    //從該節點出去的轉換弧計數
    Trans *trans;//用單鏈表保存所有的轉換弧
} State ,*PState;

//NFA類型定義
typedef struct NFANODE
{
    PState *NodeTable;//[Max_State]; //存放所有狀態的數組
    int numOfStates;//總的狀態數
    int numOfTrans;//總的轉換弧條數
    PState pStart;//NFA的start state
    PState pFinal;//NFA的final state
} NFA;

//DFA類型定義
typedef struct DFANODE
{
    int **DStates;//DFA狀態表
    int **Dtrans;//DFA轉移表
    int *AcceptSet;//DFA的接受狀態集合
    int numofDStates;//DFA的狀態計數
    int numOfDTrans;//DFA的轉移計數
} DFA;

// 定義鏈式字符棧結點
typedef struct  CHARSTACK
{      
    char data;
    struct CHARSTACK *next;
} SNode ,*PSNode;

// 定義鏈式Nfa棧（狀態棧）結點
typedef struct  STATESTACK
{      
    PState data;
    struct STATESTACK *next;
} Nfa_SNode ,*PNfa_SNode;



//全局變量
char Alphabet[Max_alphabet];
char Operator[3]={'|','*','+'};
int NumOfSymbol;
char Regexp[Max_regexp];
char Postfix[Max_regexp];
PSNode SymbStack;
PNfa_SNode StateStack;
NFA *Nfa;
DFA Dfa;
FILE *fpout;

int Readalphabet(void);//讀入字母表
int Readregexp(void);//讀入正則表達式

void Init_SymbStack(void);//字符棧初始化
int  IsEmpty_SymbStack(void);// 判斷字符棧是否為空
void Push_SymbStack(char x);// 字符棧數據入棧
char Pop_SymbStack(void);// 字符棧數據出棧
char GetTop_SymbStack(void);// 獲取字符棧棧頂數據
void Destory_SymbStack(void);// 字符棧的析構函數

void Init_StateStack(void);//狀態棧初始化
//int  IsEmpty_StateStack(void);// 判斷狀態棧是否為空
void Push_StateStack(PState x);// 狀態棧數據入棧
PState Pop_StateStack(void);// 狀態棧數據出棧
void Destory_StateStack(void);// 狀態棧的析構函數

int LexScan(char *x);//正則式的合法性檢測
int IsInArray(char x, char *charArray);//在charArray[]中查找x，成功返回1，失敗返回0，用于合法性檢測
void AddConcatenation();//正則式加入連接符“+” （代表concatenation運算符）
void REtoPostfix(void);//將正則式轉為后綴表達式
void Init_Nfa(void);//Nfa的初始化
void ConstructNFA(void);//用Thompson算法構造NFA
void NewState(PState x);//申請新的狀態點
void AddTrans(PState s1,PState s2,char x);//添加轉換弧
void OutputNFA();//輸出NFA
void BubbleSort(int *array);// 對狀態集進行排序，方便比較數組，使輸出形式更好看。
int CompArray(int *t1, int *t2);//比較兩個一維數組是否含有完全相同的元素
int* TransX(int *T, char x);// 對狀態集T中包含的某個NFA狀態求 x 轉換的狀態集合
int* Closures(int *T);//對狀態集T中包含的某個NFA狀態S求ε閉包
void ConstructDFA();//采用子集構造法構造DFA
void OutputDFATable();//輸出DFA表格
void OutputDFA();//輸出DFA的各種狀態概要，并調用void OutputDFATable()輸出DFA
void OutputSet_Array(int* array);//輸出數組 共計27個字符位
int Optimize();//去掉只有入度沒有出度的非接受狀態
int Simplify();//將DFA最簡化__最大等價狀態集法


/*______________________________讀入字母表______________________________*/ 
//將字母表讀入到全局變量中，成功返回1，失敗返回0。                            
int Readalphabet()
{
    FILE *fp;
    int i=0;
    char temp;

    printf(" ___________________________Initialization__________________________\n");
    fprintf(fpout," ___________________________Initialization__________________________\n");
    fp=fopen(FileAlphabetPath,"r");
    if (fp==NULL)
        return 0;
    printf(" The alphabet is: ");
    fprintf(fpout," The alphabet is: ");
    while( !feof(fp) )
    {
       temp=fgetc(fp);
        if((temp!=',')&&(temp!=' ')&&(temp!=10)&&(temp!=13)&&(temp!=-1))//10 換行 13回車 
        {
            Alphabet[i]=temp;
            i++;
        }
    }
    NumOfSymbol=i;//記住實際的symbol的個數
    for (i=0;i<NumOfSymbol-1;i++)
    {
        printf("%c,",Alphabet[i]);
        fprintf(fpout,"%c,",Alphabet[i]);
    }
    printf("%c\n",Alphabet[i]);
    fprintf(fpout,"%c\n",Alphabet[i]);

    printf(" The total number of symbols is: %d\n",NumOfSymbol);
    fprintf(fpout," The total number of symbols is: %d\n",NumOfSymbol);
    fclose(fp);
    return 1;
}                                                                           

/*____________________________讀入正則表達式____________________________*/ 
//將正則表達式讀入到全局變量中，成功返回1，失敗返回0。
int Readregexp()
{
    FILE *fp;

    fp=fopen(FileRegexpPath,"r");
    if (fp==NULL)
        return 0;
    fscanf(fp,"%s",Regexp);
    printf(" The regular express is: %s\n",Regexp);
    fprintf(fpout," The regular express is: %s\n",Regexp);
    fclose(fp);
    return 1;
}





/*____________________________正則式合法性驗證____________________________*/ 
//詞法掃描，正則式合法性驗證
int LexScan(char *x)
{
 int i;
 for(i=0;x[i]!='\0';i++)
 {
  if(x[i]=='(')
   Push_SymbStack(x[i]);
  else if (x[i]==')')
  {
   if(Pop_SymbStack()=='$')
    return 0;
  }
  else 
  {
   if(IsInArray(x[i], Alphabet)==0)
    if(IsInArray(x[i], Operator)==0)
     return 0;
  }
 }
 if(!IsEmpty_SymbStack)
 {
  printf("\nNumber of \"(\" and \")\" is not march!\n");
  fprintf(fpout,"\nNumber of \"(\" and \")\" is not march!\n");
  return 0;
 }
 return 1;
}
//在charArray[]中查找x，成功返回1，失敗返回0
int IsInArray(char x, char *charArray)
{
 int i,flag;
 flag=0;
 for(i=0 ; charArray[i] != '\0' ; i++)
 { if(charArray[i]==x)
   return 1;
 }
 return 0;
}
/*____________________________棧操作實現____________________________*/ 
void Init_SymbStack()//字符棧初始化
{
 SymbStack=(PSNode) malloc(sizeof(SNode));
 SymbStack->data=0;
 SymbStack->next=NULL;
}
void Init_StateStack()//狀態棧初始化
{
 StateStack=(PNfa_SNode) malloc(sizeof(Nfa_SNode));
 StateStack->data=NULL;
 StateStack->next=NULL; 
}

void Push_SymbStack(char x)// 字符棧數據入棧
{
 PSNode temp=(PSNode) malloc(sizeof(SNode));
 temp->data=x;
 temp->next=SymbStack;
 SymbStack=temp;
}

void Push_StateStack(PState x)// 狀態棧數據入棧
{
 PNfa_SNode temp=(PNfa_SNode) malloc(sizeof(Nfa_SNode));
 temp->data=x;
 temp->next=StateStack;
 StateStack=temp;
}
int  IsEmpty_SymbStack(void)// 判斷字符棧是否為空，空返回1，非空返回0。
{
 if (! SymbStack)
  return 1;
 else return 0;
}
int  IsEmpty_StateStack(void);// 判斷狀態棧是否為空
char Pop_SymbStack(void)// 字符棧數據出棧
{
 if (! IsEmpty_SymbStack())
 {
  char x;
     PSNode temp=SymbStack;
  SymbStack=SymbStack->next;
  x=temp->data;
  free(temp);
  return x;
 }
 else
 {
  printf("The stack is empty!\n");
  return '$';
 }
}
PState Pop_StateStack(void)// 狀態棧數據出棧
{
 if (StateStack)
 {
  PState x;
     PNfa_SNode temp=StateStack;
  StateStack=StateStack->next;
  x=temp->data;
  free(temp);
  return x;
 }
 else
 {
  printf("The stack is empty!\n");
  getchar();
  exit(1);
 }
}
char GetTop_SymbStack(void)// 取字符棧棧頂數據
{
 if (! IsEmpty_SymbStack())
 {
  return SymbStack->data;
 }
 else
 {
  printf("The stack is empty!\n");
  return '$';
 }
}

void Destory_SymbStack()// 字符棧析構函數
{
 PSNode temp=(PSNode) malloc(sizeof(SNode));
 while (SymbStack)
 {
  temp=SymbStack;
  SymbStack=SymbStack->next;
  free(temp);
 }
}
void Destory_StateStack(void)// 狀態棧的析構函數
{
 PNfa_SNode temp=(PNfa_SNode) malloc(sizeof(Nfa_SNode));
 while (StateStack)
 {
  temp=StateStack;
  StateStack=StateStack->next;
  free(temp);  
 }
}
 

 

 




// 定義運算符的優先級
int Precedence(char symbol)
{
    int p;
    switch (symbol)
    {
    case '|': p=1; break;
    case '+': p=2; break;
    case '*': p=3; break;
    default:  p=0; break;
    }
    return p;
}
/*____________________________正則式加"+"運算符_____________________________*/ 
//加入連接符 concatenation
void AddConcatenation()
{
 int i=0, j, len=strlen(Regexp);
 while (Regexp[i+1] != '\0')
 {
  if (((Regexp[i] != '(' && Regexp[i] != '+' && Regexp[i] != '|') 
   || Regexp[i]==')' || Regexp[i]=='*')
   && (Regexp[i+1] != ')' && Regexp[i+1] != '+' && Regexp[i+1] != '|' && Regexp[i+1] != '*'))
  {
   for (j=len; j>i+1; j--)
    Regexp[j]=Regexp[j-1];
   Regexp[i+1]='+';
   len++;
   Regexp[len]='\0';
   i++;
  }
  i++;
 }
}
/*____________________________正則式轉后綴表達式_____________________________*/ 
// 將正則式轉為后綴表達式
void REtoPostfix()
{
 int i=0, j=0;
 char curr, ctop;
 Init_SymbStack();
 curr=Regexp[i];
 while (curr != '\0')
 {
  if (curr=='(')
  {
   Push_SymbStack(curr);
   curr=Regexp[++i];
  }
  else if (curr==')')
  {
   while (GetTop_SymbStack() != '(')
   {
    Postfix[j++]=Pop_SymbStack();
   }
            Pop_SymbStack();
   curr=Regexp[++i];
  }
  else if ( (curr=='+') || (curr=='|') || (curr=='*') )
  {
      ctop=GetTop_SymbStack();
      while (Precedence(ctop) >= Precedence(curr))
   {
       Postfix[j++]=ctop;
       Pop_SymbStack();
       ctop=GetTop_SymbStack();
   }
   Push_SymbStack(curr);
   curr=Regexp[++i];
  }
  else
  {
   Postfix[j++]=curr;
   curr=Regexp[++i];
  }
 }
 curr=Pop_SymbStack();
 while ( (curr=='+') || (curr=='|') || (curr=='*'))
 {
  Postfix[j++]=curr;
  curr=Pop_SymbStack();
 }
 Postfix[j]='\0';
 Destory_SymbStack();
 printf("\nThe postfix is: %s\n",Postfix);
}

/*____________________________用Thompson算法構造NFA____________________________*/
void ConstructNFA()
{
 int i=0;
 char curr=Postfix[i];
 PState s1,s2,s3,s4,s5,s6;
 Init_StateStack();
 while(curr!='\0')
 {
  if(curr=='+')//對+運算進行處理
  {
   s4=Pop_StateStack();
   s3=Pop_StateStack();
   s2=Pop_StateStack();
   s1=Pop_StateStack();
   AddTrans(s2,s3,'~');
   Push_StateStack(s1);
   Push_StateStack(s4);
  }
  else if(curr=='|')//對|運算進行處理
  {
   s4=Pop_StateStack();
   s3=Pop_StateStack();
   s2=Pop_StateStack();
   s1=Pop_StateStack();
   s5=(PState)malloc(sizeof(State));
   NewState(s5);
   s6=(PState)malloc(sizeof(State));
   NewState(s6);
   AddTrans(s5,s1,'~');
   AddTrans(s5,s3,'~');
   AddTrans(s2,s6,'~');
   AddTrans(s4,s6,'~');
   Push_StateStack(s5);
   Push_StateStack(s6);
  }
  else if(curr=='*')//對*運算進行處理
  {
   s2=Pop_StateStack();
   s1=Pop_StateStack();
   s3=(PState)malloc(sizeof(State));
   NewState(s3);
   s4=(PState)malloc(sizeof(State));
   NewState(s4);
   AddTrans(s3,s1,'~');
   AddTrans(s2,s4,'~');   
   AddTrans(s2,s1,'~');
   AddTrans(s3,s4,'~');
   Push_StateStack(s3);
   Push_StateStack(s4);
  }
  else//對symbol進行處理 
  {
   s1=(PState)malloc(sizeof(State));
   NewState(s1);
   s2=(PState)malloc(sizeof(State));
   NewState(s2);
   AddTrans(s1,s2,curr);
   Push_StateStack(s1);
   Push_StateStack(s2);
  }
  curr=Postfix[++i];
 }
 Nfa->pFinal=Pop_StateStack();