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

char stack[100];
int top = -1;
char input[100];
int i = 0;

void printStack()
{
  for (int j = 0; j <= top; j++)
    printf("%c", stack[j]);
  printf("\n");
}

void push(char c)
{
  stack[++top] = c;
}

void pop()
{
  if (top >= 0)
    top--;
}

int tryReduce()
{
  // Rule: E → (E)
  if (top >= 2 &&
      stack[top] == ')' &&
      stack[top - 1] == 'E' &&
      stack[top - 2] == '(')
  {
    top -= 3;
    push('E');
    return 1;
  }

  // Rule: E → E*E
  if (top >= 2 &&
      stack[top] == 'E' &&
      stack[top - 1] == '*' &&
      stack[top - 2] == 'E')
  {
    top -= 3;
    push('E');
    return 1;
  }

  // Rule: E → E+E
  if (top >= 2 &&
      stack[top] == 'E' &&
      stack[top - 1] == '+' &&
      stack[top - 2] == 'E')
  {
    top -= 3;
    push('E');
    return 1;
  }

  // Rule: E → id
  if (top >= 0 && stack[top] >= 'a' && stack[top] <= 'z')
  {
    pop();
    push('E');
    return 1;
  }

  return 0;
}

int main()
{
  printf("Enter an expression: ");
  fgets(input, sizeof(input), stdin);

  while (input[i])
  {
    if (isspace(input[i]))
    {
      i++;
      continue;
    }
    push(input[i]);
    i++;
    printf("Shift: ");
    printStack();
    while (tryReduce())
    {
      printf("Reduce: ");
      printStack();
    }
  }
  if (top == 0 && stack[0] == 'E')
    printf("String Accepted\n");
  else
    printf("String Rejected\n");

  return 0;
}