#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>
#include<process.h>
class stack
{
      int s[100];
      int top;

      public:
      stack()
      {
	     top = -1;
      }

      void push(char ele)
      {
	   top++;
	   s[top]=ele;
	   //cout<<"\n push :"<<ele;
      }
      char pop()
      {
	   char ele = s[top];
	   top--;
	   //cout<<"\n pop :"<<ele;
	   return ele;
      }

      char rtop()
      {
	   return s[top];
      }
      char val();

};

int nter(char)            ;
char stack::val() 	//this will give the top terminal of the stack
      {
	   int t=top;
	   while(nter(s[t])!=-1)
	   {
		t--;
	   }
	   return s[t];
      }

int f(char op)
{
	switch(op)
	{
		case '+': return 2;
		case '*': return 4;
		case '$': return 0;
		case 'i': return 4;
		default: return -1;
	}
}

int g(char op)
{
	switch(op)
	{
		case '+': return 1;
		case '*': return 3;
		case '$': return 0;
		case 'i': return 5;
		default: return -1;
	}
}
int ter(char op)	//check for terminals
{
	switch(op)
	{
		case '+': return 0;
		case '*': return 1;
		case '$': return 2;
		case 'i': return 3;
		default: return -1;
	}
}
int nter(char op)    //check for nonterminals
{
	switch(op)
	{
		case 'E': return 0;
		default: return -1;
	}
}

void main()
{
	clrscr();
	char prod[][10]={"E+E","E*E","i"};   //RHS of production rules
	char input[100];

	cout<<"\nEnter input string(end with $): ";
	cin>>input;

	stack st;
	st.push('$');


	for(int i=0;input[i] != '\0';)   //loop for scanning input
	{
	     char stop = st.val();      //getting the top terminal of the stack

	     if(ter(input[i])==-1)      //if input is not a terminal then error
	     {
		cout<<"\nInvalid Input : "<<input[i];
		getch();
		exit(0);
	     }

	     if(stop=='$'&&input[i]=='$')      //when both top of stack and input are $ then accept
	     {
		cout<<"\n\nString Accepted";
		getch();
		exit(0);
	     }

	     if(f(stop)<=g(input[i])) 	//if top of stack has less precedance then input
	     {
		st.push(input[i]);     //shift
		i++;                   //point to next input char
	     }
	     else
	     {
		char *handle;
		int r=0;
		int flag=0;
		int r1=-1;

		while(1)    //loop to make handle by popping
		{
			char t=st.rtop();  //top of stack

			if(nter(t)!=-1)   //if top of stack is non ter
			{
			       handle[r]=st.pop();    //add to handle
			       //cout<<endl<<handle[r];
			       r++;
			}
			else
			{
				if(r1==-1)         //when first terminal is encountered
				{
				   if(f(t)>g(input[i]))   //compare with input
				   {
					handle[r]=st.pop();
					r1=r;
					r++;
				   }
				   else
					flag=1;
				}
				else if(f(t)>g(handle[r1]))  //compare with last terminal of handle
				{
				   handle[r]=st.pop();
				   r1=r;  //storing index of last terminal of handle
				   r++;
				}
				else   //when top of stack has less precedance
				{
					flag=1;   //handle complete
				}
			}
			if(flag)
			{
				break;
			}
		}

		handle[r]='\0';

		int p=-1;

		for(int m=0;m<3;m++) //finding the prod rule matching the handle
		{

			int y=strcmp(prod[m],handle);

			if(y==0)      //if match found
			{
				p=m;
				//cout<<"\np="<<p;
				break;
			}

		}
		if(p==-1) //if no prod rule found
		{
			cout<<"\n Invalid String!!";
			getch();
			exit(0);
		}
		else    //if prod rule found
		{
			cout<<"\n "<<prod[m]<<" -> E\n";     //print prod rule
			st.push('E');       //push LHS i.e E for every rule in this case
		}


	     }
     }
     cout<<"\n Invalid input : insert $ at end of input";
    getch();

}