#include "stdio.h"  
#include "malloc.h"  

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

int table[8][8]={{1,1,-1,-1,-1,1,-1,1},  
    {1,1,-1,-1,-1,1,-1,1},  
    {1,1,1,1,-1,1,-1,1},  
    {1,1,1,1,-1,1,-1,1},  
    {-1,-1,-1,-1,-1,-1,-1,0},  
    {1,1,1,1,0,1,0,1},  
    {1,1,1,1,0,1,0,1},  
    {-1,-1,-1,-1,-1,0,-1,-1}};  
//存儲(chǔ)算符優(yōu)先關(guān)系表，大于為1，小于或等于為-1，其它為0表示出 

char curchar;  
char curcmp;  
int right;  /*設(shè)置開關(guān)項(xiàng)，當(dāng)出錯(cuò)時(shí)為0*/  
int i,j;  
int k;      /*比較字符在棧的位置*/  

void push(char pchar)  /*入棧函數(shù)*/  
{  
 temp=(Lchar*)malloc(sizeof(LLchar));  
 temp->char_ch=pchar;  
 temp->next=top;  
 top=temp;  
}  

void pop(void)  /*出棧函數(shù)*/  
{  
 if(top->char_ch!='#')  
  top=top->next;  
}  

int changchartoint(char ch)  /*將字符轉(zhuǎn)為數(shù)字，以得到算符優(yōu)先值*/  
{  
 int t;  
 switch(ch)  
 {  
  case '+':t=0;break;  
  case '-':t=1;break;  
  case '*':t=2;break;  
  case '/':t=3;break;  
  case '(':t=4;break;  
  case ')':t=5;break;  
  case 'i':t=6;break;  
  case '#':t=7;  
 }  
 return t;  
}  

void dosome(void)  
{  
 k=1;  
 for(;;)  
 {  
  curchar=h->char_ch;  
  temp=top;  
  for(;;)  
  {  
   if(temp->char_ch=='N')  
   {  
  nbs;
  p;
  temp=temp->next;  
    k++;  
   }  
   else  
   {  
    curcmp=temp->char_ch;  
    break;  
   }  
  }  
  printf("\n%d\t%d\t",table[i][j],k);  
  temp=top;  
  for(;;)    /*打印棧*/  
  {  
   printf("%c",temp->char_ch);  
   if(temp->char_ch=='#')  
    break;  
   else  
    temp=temp->next;  
  }  
  printf("\t");  
  temp=h;  
  for(;;)    /*打印待比較的字符*/  
  {  
   printf("%c",temp->char_ch);  
     
   if(temp->char_ch=='#')  
    break;  
   else  
    temp=temp->next;  
  }  
  i=changchartoint(curcmp);  
  j=changchartoint(curchar);  
  if(table[i][j]==0)  /*算符優(yōu)先值為空*/  
  {  
   printf("\n%d\t%d\t%c\t%c\terror1",table[i][j],k,curcmp,curchar);  
   right=0;  
   break;  
  }  
  else                 /*算符優(yōu)先值不為空*/  
  {  
   if(table[i][j]<0)   /*算符優(yōu)先值為-1，移進(jìn)*/  
   {  
    if(curchar=='#')   /*待比較字符為空*/  
    {  
     if(k==2)          /*當(dāng)前比較字符在棧的位置為兩個(gè)元素*/  
      break;  
     else  
     {  
      printf("\n%d\t%d\t%c\t%c\terror2",table[i][j],k,curcmp,curchar);  
      right=0; 
      break;  
     }  
    }  
    push(curchar);  
    k=1;  
    curcmp=curchar;  
    h=h->next;  
   }  
   else              /*算符優(yōu)先值為1，歸約*/  
   {  
    if(curcmp=='i')  /*當(dāng)前比較為i,出棧一次*/  
     pop();  
    else             /*當(dāng)前比較不為i,出棧三次*/  
    {  
     pop();  
     pop();  
     pop();  
    }  
    push('N');       /*歸約到N*/  
    k=1;  
   }  
  }  
 }  
}  
void main(void)  
{  
 char ch;  
 right=1;  
 base=(Lchar*)malloc(sizeof(LLchar));  
 base->next=NULL; 
 base->char_ch='#';  
 top=base;  
 h=(Lchar*)malloc(sizeof(LLchar));  
 h->next=NULL;  
 p=h;  
 do{                 /*輸入待比較字符串，以'#'結(jié)束*/  
  ch=getchar();  
  putchar(ch); 	  
  if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')  
  {  
   temp=(Lchar*)malloc(sizeof(LLchar));  
   temp->next=NULL;  
   temp->char_ch=ch;  
   h->next=temp;  
   h=h->next;  
  }  
  else  
  {  
   temp=p->next;  
   printf("\nInput a wrong char!Input again:\n");  
   for(;;)  
{      
    if (temp!=NULL)  
     printf("%c",temp->char_ch);        
    else  
     break;  
    temp=temp->next;  
   }  
  }  
 }while(ch!='#');      /*輸入待比較字符串，以'#'結(jié)束*/  
 p=p->next;  
 h=p;  
 dosome();             /*開始識(shí)別*/  
 if(right)  
  printf("\nOK!\n");  
 else  
  printf("\nError!\n");  
 getchar();  
}