#include<ctype.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<iostream.h>
struct danci
  {
	  int id;			//單詞種別
	  char name[10];	//單詞屬性值
  };
int fout[20];
int index=1;
int G_table[9][6];
int k[20];
int n=0;
danci word[20];
int boo(int);
int compare(int);
int not(int);
int forid(int);
typedef struct node{
	int data; 
   	node* next;
 }* link;
link insert(link stack,int n)//向前插入鏈表
{
	link newnode;
	newnode=new node;
	if(!newnode)
	{
		cout<<"error!"<<endl;
		exit(0);
	}
	newnode->data=n;
	newnode->next=stack;
	stack=newnode;
	return stack;
}
link del(link stack,int &value)//刪除鏈表元素
{
	link top;
	if(stack)
	{
		top=stack;
		stack=stack->next;
		value=top->data;
		delete top;
		return stack;
	}
	value=-1;
	return NULL;
}
void error()
{
	cout<<"詞法錯誤,標志符不能以數字開頭"<<endl;
	exit(0);
}
void error1()
{
	cout<<"語法錯誤,輸入正確句子"<<endl;
	exit(0);
}
int not(int i)
{
	int ii;
	i=forid(i);
	while(word[i].id==3)
	{
		ii=i;
		i++;
		i=forid(i);
		fout[index]=ii;
		index++;
	}
	return i;
}
void init()//初始化文法矩陣
{
	for(int i=0;i<9;i++)               	
	for(int j=0;j<6;j++)
		G_table[i][j]=-1;
	G_table[0][0]=0;G_table[0][1]=1; //初始化文法表
	G_table[1][0]=1;G_table[1][1]=1;G_table[1][2]=5;G_table[1][3]=2;
	G_table[2][0]=1;G_table[2][1]=2;
	G_table[3][0]=1;G_table[3][1]=1;G_table[3][2]=3;
	G_table[4][0]=2;G_table[4][1]=3;
	G_table[5][0]=3;G_table[5][1]=6;G_table[5][2]=3;
	G_table[6][0]=3;G_table[6][1]=9;G_table[6][2]=1;G_table[6][3]=10;
	G_table[7][0]=3;G_table[7][1]=7;
	G_table[8][0]=3;G_table[8][1]=9;G_table[8][2]=7;G_table[8][3]=8;
	G_table[8][4]=7;G_table[8][5]=10;
}
void print()//打印文法
{   
char a0[]="E";char a1[]="S";
char a2[]="B";char a3[]="C";
char a4[]="and";char a5[]="or";
char a6[]="not";char a7[]="id";
char a8[]="relop";char a9[]="(";
char a10[]=")";
cout<<"本實驗的文法為："<<endl;
cout<<a0<<"->"<<a1<<endl;
cout<<a1<<"->"<<a1<<' '<<a5<<a2<<endl;
cout<<a1<<"->"<<a2<<endl;
cout<<a2<<"->"<<a2<<' '<<a4<<' '<<a3<<endl;
cout<<a2<<"->"<<a3<<endl;
cout<<a3<<"->"<<a6<<' '<<a3<<endl;
cout<<a3<<"->"<<a9<<a1<<a10<<endl;
cout<<a3<<"->"<<a7<<endl;
cout<<a3<<"->"<<a9<<a7<<' '<<a8<<' '<<a7<<a10<<endl; 
}
int  lex(char * buf)//詞法分析
{
	int i=0,j=0;
	int n=0;
	char Temp_name[10];
	while(buf[i]!='\0')
	{
		if(buf[i]==' '||buf[i]=='\n')
			i++;
		else if(isalpha(buf[i])||buf[i]=='_')//標志符判斷
		{
			Temp_name[j]=buf[i];
			i++;
			while(isalnum(buf[i]))
			{
				j++;
				Temp_name[j]=buf[i];
				i++;
			}
		   // if
			memcpy(word[n].name,Temp_name,j+1);
			word[n].name[j+1]='\0';
			if(strcmp(word[n].name,"and")==0)
				word[n].id=1;
			else if(strcmp(word[n].name,"or")==0)
				word[n].id=2;
			else if(strcmp(word[n].name,"not")==0)
				word[n].id=3;
			else 
				word[n].id=0;
			n++;
			j=0;
		}
		else if(isdigit(buf[i]))//數字判斷
		{
			while(isdigit(buf[i]))
			{
			Temp_name[j]=buf[i];
			i++;
			j++;
			}
				if(isalpha(buf[i]))
                  error();
			memcpy(word[n].name,Temp_name,j+1);
			word[n].name[j]='\0';
			n++;
			j=0;
		}
		else//運算符號判斷
		{
			switch(buf[i])
			{
				case '>':if(buf[i+1]=='=')
						 {
							  i++;
						   	  word[n].id=8;
							  strcpy(word[n].name,">=");
						 }
						 else
						 {
							 word[n].id=4;
							 strcpy(word[n].name,">");
						 }
						 n++;break;
				case '<':if(buf[i+1]=='=')
						 {
							  i++;
						   	  word[n].id=9;
							  strcpy(word[n].name,"<=");
						 }
						 else 
						 {
							 word[n].id=5;
							 strcpy(word[n].name,"<");
						 }
						 n++;break;
				case '=': word[n].id=6;strcpy(word[n].name,"=");n++;break;
				case '!': if(buf[i+1]=='=')
						  {
							  i++;
						   	  word[n].id=7;strcpy(word[n].name,"!=");
							  n++;
						  }
						   break;
				case '(': word[n].id=10;strcpy(word[n].name,"(");n++;break;
				case ')': word[n].id=11;strcpy(word[n].name,")");n++;break;
			}
			i++;
		}
	}
	strcpy(word[n].name,"#");
		word[n].id=999;
	return n;//單詞符號個數
}

void gram(int * kind)
{
	int n=0;
	link state;	                    
	link lex;                      
	link operate;						
	link ID;						
	state=new node[30];lex=new node[15];
	if(!state||!lex)                
	{
		cout<<"over stack! "<<endl;
		exit(0);
	}
	int trace=0;					
	int G[9][5];					
	int Stable[16][11];			//SLR分析表
	int i,j;
	for(i=0;i<9;i++)               	
		for(j=0;j<5;j++)
			G[i][j]=-1;
	for(i=0;i<18;i++)
		for(j=0;j<11;j++)
			Stable[i][j]=0;		//初始化SLR表，其中表的初值為0，表示出錯！								
	//設置SLR表 1-17表示移進，n進狀態棧;21-29表示按N-20個產生式規約；0表示出錯
	Stable[0][2]=4;Stable[0][3]=5;Stable[0][6]=6;
	Stable[0][8]=1;Stable[0][9]=2;Stable[0][10]=3;
	Stable[1][0]=7;Stable[1][7]=111;
	Stable[2][0]=23;Stable[2][1]=8;Stable[2][4]=23;Stable[2][7]=23;
	Stable[3][0]=25;Stable[3][1]=25;Stable[3][4]=25;
	Stable[3][7]=25;
	Stable[4][2]=4;Stable[4][3]=5;Stable[4][6]=6;Stable[4][10]=9;
	Stable[5][2]=4;Stable[5][3]=5;Stable[5][6]=11;
	Stable[5][8]=10;Stable[5][9]=2;Stable[5][10]=3;
	Stable[6][0]=28;Stable[6][1]=28;Stable[6][4]=28;Stable[6][7]=28;
	Stable[7][2]=4;Stable[7][3]=5;Stable[7][6]=6;
	Stable[7][9]=12;Stable[7][10]=3;
	Stable[8][2]=4;Stable[8][3]=5;	Stable[8][6]=6;Stable[8][10]=13;
	Stable[9][0]=26;Stable[9][7]=26;Stable[9][4]=26;Stable[9][1]=26;
	Stable[10][0]=7;Stable[10][4]=14;
	Stable[11][0]=28;Stable[11][1]=28;
	Stable[11][4]=28;Stable[11][5]=15;Stable[11][7]=28;
	Stable[12][0]=22;Stable[12][1]=8;Stable[12][4]=22;Stable[12][7]=22;
	Stable[13][1]=4;Stable[13][2]=4;Stable[13][3]=4;
	Stable[13][0]=24;Stable[13][1]=24;Stable[13][4]=24;Stable[13][7]=24;
	Stable[14][0]=27;Stable[14][1]=27;Stable[14][4]=27;Stable[14][7]=27;
	Stable[15][6]=16;Stable[16][6]=17;
	Stable[17][0]=29;Stable[17][1]=29;Stable[17][4]=29;Stable[17][7]=29;
	kind[n]=7;								//輸入串最后字符為#
	n++;
	state=insert(state,0);
	lex=insert(lex,7);
	int a;
	int staTop;								//存放狀態棧的棧頂元素
	int operater;int ch1=0;int ch2;
	for(a=0;a<n;a++)						//進行SLR分析
	{
		staTop=state->data;
	  if(Stable[staTop][kind[a]]==0)
		{

			break;
				
		}
	 else if(Stable[staTop][kind[a]]<20)
		{			//規約
			int sta1;
			int letter1;
			if(state!=NULL)
				state=del(state,sta1);
			else 
			{
             error1();
			}
			int num=0;					//出棧次數
			int b;
			for(b=1;b<G_table[Stable[staTop][kind[a]]][4];b++)
			{							//規約式右部出棧
				lex=del(lex,letter1);
				num++;
			}
			lex=insert(lex,G_table[Stable[staTop][kind[a]]][0]);//規約式左部進棧
			for(b=1;b<num;b++)			//狀態棧中再出棧num-1個狀態
				state=del(state,sta1);
			int staTop1;
			staTop1=state->data;
			state=insert(state,Stable[staTop1][G_table[Stable[staTop][kind[a]]][0]]-50);
			a--;
			if(num>1)
			{	
				if(ch1==0)//總結符
				{
					ID=del(ID,ch1);
					ch1=trace;trace--;
				}
				else
					ch1=-1;
				operate=del(operate,operater);
				ID=del(ID,ch2);
				ch2=trace;trace--;
				ch1--;
			}
		}
    	else if(Stable[staTop][kind[a]]<50)
		{//移進一個符號
			state=insert(state,Stable[staTop][kind[a]]-20);
			lex=insert(lex,kind[a]);
			if(kind[a]==0)
			{
				trace++;
				ID=insert(ID,kind[a]);
			}
			else
				operate=insert(operate,kind[a]);
		}
		else if(Stable[staTop][kind[a]]==99)
		{
			cout<<endl;
			cout<<"ACCEPT!"<<endl;
			break;
		}
	
	}
}
void forboland(int length)
{
	
	int i=0;
	while((i<length)&&(word[i].id!=99))
	{
		i=boo(i);
		if(word[i].id==99)
		{
         error1();
		}
	}

}
int boo (int i)
{
	int ii;
	i=compare(i);
	while (word[i].id==1||word[i].id==2)
	{
		ii=i;
		i++;				
		i=compare(i);	
		fout[index]=ii;//
		index++;
	}
	return i;
}

int forid(int i)
{
	if (word[i].id==0)		
	{
		fout[index]=i;
		index++;
		i++;
	}
    else
	{
		if(word[i].id==10)
		{
			i++;				
			i=boo(i);
			if (word[i].id==11)
				i++;			
			else
				word[i].id=99;
		}
		else if(word[i].id==3)
		{;}
		else
		{
            error1();
			word[i].id=99;
		}
	}
	return i;
}
void boland()
{
	for(int i=1;i<index;i++)
	{
		if(word[fout[i]].id==0)
			cout<<word[fout[i]].name<<" ";
		else
		{
			switch (word[fout[i]].id)
			{
			case 1: cout<<"and ";break;
			case 2: cout<<"or ";break;
			case 3: cout<<"not ";break;
			case 4: cout<<"> ";break;
			case 5: cout<<"< ";break;
			case 6: cout<<"= ";break;
			case 7: cout<<"!= ";break;
			case 8: cout<<">= ";break;
			case 9: cout<<"<= ";break;
			}
		}
	}
	index=0;
 }
int compare(int i)
{
	int ii;
	i=not(i);
	while(word[i].id==4||word[i].id==5||word[i].id==6
		||word[i].id==7||word[i].id==8||word[i].id==9)
	{
		ii=i;
		i++;				
		i=not(i);
		fout[index]=ii;
		index++;
	}
	return i;
}
void main()
{
	char buffer[30];
	int i=0;
	int length;
	char *inword;
	init();
	print();
	cout<<"輸入布爾表達式，以#結束 :"<<endl;
	cin>>buffer[i];
	while(buffer[i]!='#')
	{
		i++;
		cin.get(buffer[i]);
	}
	buffer[i]='\0';
	length=i+1;
	inword=new char[length];
	memcpy(inword,buffer,length);
	length=lex(inword);
	cout<<"詞法分析結果如下："<<endl;
	cout<<'('<<"屬性"<<' '<<"值"<<')';
	for( i=0;i<length;i++)
	{	cout<<'('<<word[i].id<<' '<<word[i].name<<')'; cout<<' ';}
	cout<<endl;

	n=length;
	forboland(length);
	gram(k);
	cout<<"逆波蘭式為：\n"<<endl;
	//逆波蘭式翻譯
	boland();
	cout<<endl;
}