/********************************************/
/*            程序相關(guān)說明
/*  
/*  列     0=E  1=G  2=T  3=S  4=F  
/*  行 0=i  1=+  2=-  3=*  4=/  5=(  6=)  7=# 
/********************************************/


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

#define true 1

typedef struct LLchar
{
    char char_ch;
    struct LLchar *next;
} Lchar;
Lchar *p,*h,*temp,*top,*base;

char curchar;
char curtocmp;
int right;
int i,j,table_index;
int print_index;

int table[5][8] =
{
   /*i + - * / ( ) #*/
    {1,0,0,0,0,1,0,0},//E
    {0,1,1,0,0,0,1,1},//G
    {1,0,0,0,0,1,0,0},//T
    {0,1,1,1,1,0,1,1},//S
    {1,0,0,0,0,1,0,0} //F
};

char* tstring[5][8] =
{ 
   /*  0    1            2          3            4          5           6           7              */
   /*  i       +            -          *            /          (           )           #              */
 {"E->TG", "ERROR",      "ERROR",  "ERROR",     "ERROR",    "E->TG",  "ERROR",     "ERROR"  },//E
 {"ERROR", "G->+TG",     "G->-TG", "ERROR",     "ERROR",    "ERROR",  "G->ε",     "G->ε"  },//G
 {"T->FS", "ERROR",      "ERROR",  "ERROR",     "ERROR",    "T->FS",  "ERROR",     "ERROR"  },//T
 {"ERROR", "S->ε",      "S->ε",  "S->*FS",    "S->/FS",    "ERROR",  "S->ε",     "S->ε" },//S
 {"F->i",  "ERROR",      "ERROR",  "ERROR",     "ERROR",    "F->(E)", "ERROR",     "ERROR"  } //F
};

/*********** 壓符號(hào)棧 ***************/
void Push(char pchar)
{
 temp=(Lchar*)malloc(sizeof(Lchar));
 temp->char_ch=pchar;
 temp->next=top;
 top=temp;
}

/*********** 彈符號(hào)棧 ***************/
void Pop(void)
{
   curtocmp=top->char_ch;
   if(top->char_ch!='#')
   top=top->next;
}
/***************** 壓棧時(shí)的規(guī)則實(shí)現(xiàn)函數(shù) ************/
void DoForPush(int t)
{
    switch(t)
    {
     case 0: Push('G');Push('T');
   printf("\t%s",tstring[i][j]);
   break;
     case 5: Push('G');Push('T');
   printf("\t%s",tstring[i][j]);
   break;
     case 11:Push('G');Push('T');Push('+');
   printf("\t%s",tstring[i][j]);
   break;
     case 12:Push('G');Push('T');Push('-');
   printf("\t%s",tstring[i][j]);
   break;
     case 20:Push('S');Push('F');
   printf("\t%s",tstring[i][j]);
   break;
     case 25:Push('S');Push('F');
   printf("\t%s",tstring[i][j]);
   break;
     case 33:Push('S');Push('F');Push('*');
   printf("\t%s",tstring[i][j]);
   break;
     case 34:Push('S');Push('F');Push('/');
   printf("\t%s",tstring[i][j]);
   break;
     case 40:Push('i');
   printf("\t%s",tstring[i][j]);
   break;
     case 45:Push(')');Push('E');Push('(');
   printf("\t%s",tstring[i][j]);
    }

}

//打印剩余的輸入串
void PrintInputString()
{
 Lchar* printinputstring;
 printinputstring=h;
 while(printinputstring!=NULL)
 {
  printf("%c",printinputstring->char_ch);
  printinputstring=printinputstring->next;
 }
}

//打印棧中的符號(hào)
void PrintStack()
{
 Lchar* printstack;
 printstack=top;
 printf("%d\t",print_index++);
    while(printstack!=NULL)
 {
  printf("%c",printstack->char_ch);
  printstack=printstack->next;
 }
}

// 根據(jù)符號(hào)棧和輸入串中的字符確定所用的表項(xiàng)
void ChangCharToint()
{
    switch(curtocmp)
    {
         case 'G':i=1;break;
         case 'S':i=3;break;
         case 'E':i=0;break;
         case 'T':i=2;break;
         case 'F':i=4;break;
    }
    switch(curchar)
    {
         case 'i':j=0;break;
         case '+':j=1;break;
         case '-':j=2;break;
         case '*':j=3;break;
         case '/':j=4;break;
         case '(':j=5;break;
         case ')':j=6;break;
         case '#':j=7;break;
    }
}

//具體的分析函數(shù)
int DoSome()
{
 int flag=1;
    while(true)
    {
  printf("\n");
  PrintStack();
  printf("\t");
  PrintInputString();
        Pop();
  
        curchar=h->char_ch;
        if(curtocmp=='#' && curchar=='#')
             break;
        if(curtocmp=='G'||curtocmp=='S'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F')
     {
            if(curtocmp!='#')
      {
                ChangCharToint();
                if(table[i][j])
          {
                 table_index=10*i+j;
                    DoForPush(table_index);
                 continue;
          }
          else
          {
                 flag=0;
              break;
          }
      }
            else if(curtocmp!=curchar)
      {
             flag=0;
             break;
      }
         else
             break;
     }
        else if(curtocmp!=curchar)
     {
             flag=0;
             break;
     }
        else
     {
            h=h->next;
            continue;
     }
    }
 return flag;
}


int main(int argc,char *argv[])
{
    char ch;
    int flag;
 print_index=0;
    base=malloc(sizeof(Lchar));
    base->next=NULL;
    base->char_ch='#';
    temp=malloc(sizeof(Lchar));
    temp->next=base;
    temp->char_ch='E';
    top=temp;
    h=malloc(sizeof(Lchar));
    h->next=NULL;
    p=h;
 printf("輸入一個(gè)以＃結(jié)束的符號(hào)串(包括+-*/()i#)\n");
    do{
            ch=getch();
            putch(ch);
            if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
      {
                temp=malloc(sizeof(Lchar));
                temp->next=NULL;
                temp->char_ch=ch;
                h->next=temp;
                h=h->next;
      }
   /****++++++++++++++出錯(cuò)提醒(warning)+++++++++++++++++++++++++*******/
         else
      {
                temp=p->next;
                printf("\nInput a wrong char!Input again:\n");
                while(true)
             {    
                    if (temp!=NULL)
                     printf("%c",temp->char_ch);      
              else
               break;
                    temp=temp->next;
          }
      }//warning

    }while(ch!='#');
    p=p->next;
    h=p;
 printf("\n步驟\t符號(hào)棧\t輸入串\t所用產(chǎn)生式");

    flag=DoSome(right);

    if(1 == flag)
        printf("\nOK!\n");
    else
        printf("\nError!\n");
    getch();
}