#include<stdio.h>
#include<conio.h>
#include<string.h>



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

int g(char c)
{
    switch(c)
    {
             case '+' : return 1;
             case '*' : return 3;
             case '(' : return 5;
             case ')' : return 0;
             case 'i' : return 5;
             case '$' : return 0;
             case 'E' : return -1;  
           
     }   
}

int check(char *c)
{
    char prod[][10] = {"E+E","E*E","(E)","i"};
    int flag=0;
   // printf("in check %s",c);
    for(int i = 0;i<4;i++)
    {
            
            if(strcmp(prod[i],c)==0)
            {
                                      printf("\nproduction rule used is : %s \n",prod[i]);
                                       flag = 1;
                                       break;
            }
    }
    
   // printf("in check flag %d",flag);
    
    return flag;
    

}    

class stack
{
      int top;
     
      char arr[20];
      
      public:
      stack()
      {
             top =  -1;
             
      }
      
      void push(char c)
      {
         top++;
         arr[top] = c;
                  
      }  
      
      char pop()
      {
           char a = arr[top];
           top--;
           return a;
      }
      
      char rtop()
      {
           return arr[top];
      }
      
      int next()
      {
          return arr[top -1];
      }
      
      void settop()
      {
           top--;
      }
   
          
};

int main()
{
    char input[20],handle[20],top;
    int i,j,flag;
    printf("\nenter the input\n");
    
    scanf("%s",input);
    stack s ;
    s.push('$');
   
    
    for(i=0;input[i] != '\0';i++)
    {
         printf("\nnow top  :%c",s.rtop());
         
         flag = 0;
         j=0;
          if((s.rtop()== 'E')&&(input[i] == '$')&&(s.next()== '$'))
          {
                         printf("\nThe string is  :  accepted\n");
          }
          else
          {
          
              if(f(s.rtop())<=g(input[i]))
              {
                    if(f(s.rtop() )== -1)
                    {
                                  if(f(s.next())<= g(input[i]))
                                  {
                                                  printf("\nwhen input is greater and not E push : %c\n ",input[i]);
                                                  s.push(input[i]);
                                                  flag =1;
                                  }
                                  else
                                  {
                                      printf("\nwhen input is smaller than stack then push E handle : %c",s.rtop()); 
                                      handle[j++] = s.rtop();
                                      s.pop();
                                     
              
                                  }
                    }
                    else 
                    {
                       printf("\nwhen input is greater then stack push : %c",input[i]);
                       s.push(input[i]);
                       flag = 1;
                    }
                       
              }
              
              if(flag == 0)
              {
                  
                 printf("\n\nNow stack is greater than input\n");
                 
                 if(f(s.rtop()) > g(input[i]))    
                 {
                               printf("\nthe top of stack is : %c  which is poped and made handle\n",s.rtop());
                               top = handle[j] = s.rtop();
                               j++;
                               s.pop();
                               
                               while(1)
                               {
                                       if(f(s.rtop()) == -1)
                                       {
                                                      printf("\nwhen top of stack is E simple add to handle : %c  and pop\n",s.rtop());
                                                      handle[j] = s.rtop();
                                                      j++;
                                                      s.pop();
                                       }
                                       else
                                       {
                                           if(f(top)>g(s.rtop()))
                                           {
                                                                printf("\nwhen top of stack is bigger : %c than currently stack element being processed:  %c",top,s.rtop());
                                                                break;
                                           }
                                           else
                                           {
                                               printf("\nwhen top of stack is smaller : %c than currently input being processed : %c",top,s.rtop());
                                               handle[j] = s.rtop();
                                               j++;
                                           }
                                       }
                               }
                               
                               handle[j] = '\0';
                               printf("\nthe handle is %s",handle); 
                               int ch = check(handle);
                               if(ch == 0)
                               {
                                        printf("\nerror\n");
                                                     break;
                               }
                               else
                                {
                                   printf("\naccepted");
                                    s.push('E');
                                     i--;
                                }
                 }
                 
              }
                       
                                       
                                
          } 
            
          
          }
                      
    
    
    getch();
    return 0;
    
    
}