// 編譯原理.cpp : 定義控制臺應用程序的入口點。
//

#include "stdafx.h"


/****************************************/
/*    算符優先分析程序 */
/****************************************/ 

struct Lchar
{
  char char_ch;
  struct Lchar *next;
}LLchar,*p,*h,*temp,*top,*base;
int table[7][7]={{0,1,1,1,0,1,1},
    {-1,1,0,-1,-1,1,1},
    {-1,-1,0,-1,-1,0,1},
    {-1,1,0,1,-1,1,1},
    {-1,-1,0,-1,-1,0,0}, 
    {0,1,0,1,0,1,1},
	{-1,0,-1,0,0,0,-1}};
//存儲算符優先關系表，大于為1，小于或等于為-1，其它為0表示出錯
char curchar;
char curcmp;
int right;  /*設置開關項，當出錯時為0*/ 
int i,j; 
int k;      /*比較字符在棧的位置*/
void push(char pchar)  /*入棧函數*/ 
{
 temp=(Lchar*)malloc(sizeof(LLchar)); 
 temp->char_ch=pchar; 
 temp->next=top; 
 top=temp;
} 
char pop(void)  /*出棧函數*/ 
{
 char c;
 c=top->char_ch;
 if(top->char_ch!='#') {
	top=top->next; 
 }
 return c;

} 
int changchartoint(char ch)  /*將字符轉為數字，以得到算符優先值*/ 
{ 
 int t; 
 switch(ch)
 { 
  case 'i':t=0;break; 
  case '+':t=1;break; 
  case '=':t=2;break;
  case '*':t=3;break; 
  case '(':t=4;break; 
  case ')':t=5; break;
  case '#': t=6;
 } 
 return t; 
}
void guiyue(){
	char tempc;
	char tempc1;
	char tempc2;
	char tempc3;
	char popc;
	tempc =	pop();
	tempc1=pop();
	if(tempc=='i')
	{
		
		if(tempc1=='#')
		{
			push('V');
			k=1;
		}
		else {
				
				switch(tempc1){
				case '+':popc='T';break;
				case '*':popc='F';break;
				case '=':popc='E';
				}
				push(tempc1);
				push(popc);
				k=1;
			}

	}
	else
	{ 
		if(tempc=='F'){
			tempc2=pop();
				if(tempc1=='*'&&tempc2=='T'){
					push('T');
				}
				else
					right=0;
			}
		else if(tempc=='T'){
			tempc2=pop();
			if(tempc1=='+'&&tempc2=='E'){
					push('E');
				}
			else
			right=0;
		}
        else if(tempc=='E'){
			tempc2=pop();
			if(tempc1=='='&&tempc2=='V'){
					push('A');
				}
			else
			right=0;
		}
		else if(tempc=='A'){
			tempc2=pop();
			if(tempc2!='#'){
				right=0;
			}
		}
		else if(tempc=='='){
			tempc2=pop();
			if(tempc1=='V'&&tempc2=='E'){
				push('A');
				
			}
			else right=0;
		}
		
    }			
}
void dosome(void) 
{ 
 k=1;
 for(;;) 
 { 
  curchar=h->char_ch; 
  temp=top;
  if(temp->char_ch=='A'){
	break;
  }
  else {
  for(;;) 
  { 
   if(temp->char_ch=='V'||temp->char_ch=='E'||temp->char_ch=='T'||temp->char_ch=='F'||temp->char_ch=='A'||temp->char_ch=='S') 
   {
    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)  /*算符優先值為空*/ 
  { 
   printf("\n%d\t%d\t%c\t%c\terror1",table[i][j],k,curcmp,curchar); 
   right=0;
   break; 
  } 
  else                 /*算符優先值不為空*/ 
  {
   if(table[i][j]<0)   /*算符優先值為-1，移進*/ 
   { 
    if(curchar=='#')   /*待比較字符為空*/ 
    {
     if(k==2)          /*當前比較字符在棧的位置為兩個元素*/ 
      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              /*算符優先值為1，歸約*/ 
   {
    guiyue();
   } 
  }
  }
 } 
} 
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{                 /*輸入待比較字符串，以'#'結束*/ 
  ch=getchar(); 
  putchar(ch);
   if(ch=='i'||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!='#');      /*輸入待比較字符串，以'#'結束*/ 
 p=p->next; 
 h=p;
 dosome();             /*開始識別*/ 
 if(right) 
  printf("\nOK!\n"); 
 else
  printf("\nError!\n"); 
 getchar(); 
 getchar();
}