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

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

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

void reduce()
{
    int changed = 1;

    while(changed)
    {
        changed = 0;

        if(top >= 0 &&
           stack[top] >= 'a' &&
           stack[top] <= 'z')
        {
            stack[top] = 'E';
            printf("Reduce: ");
            printStack();
            changed = 1;
        }

        if(top >= 2 &&
           stack[top-2] == '(' &&
           stack[top-1] == 'E' &&
           stack[top] == ')')
        {
            top -= 2;
            stack[top] = 'E';
            printf("Reduce: ");
            printStack();
            changed = 1;
            continue;
        }

        if(top >= 2 &&
           stack[top-2] == 'E' &&
           stack[top-1] == '+' &&
           stack[top] == 'E')
        {
            top -= 2;
            stack[top] = 'E';
            printf("Reduce: ");
            printStack();
            changed = 1;
            continue;
        }

        if(top >= 2 &&
           stack[top-2] == 'E' &&
           stack[top-1] == '*' &&
           stack[top] == 'E')
        {
            top -= 2;
            stack[top] = 'E';
            printf("Reduce: ");
            printStack();
            changed = 1;
            continue;
        }
    }
}

int main()
{
    int ptr = 0;
    int i, len;

    printf("Enter an Expression: ");
    fgets(input, sizeof(input), stdin);

    char exp[100];
    int j = 0;

    for(i = 0; input[i] != '\0'; i++)
    {
        if(input[i] != ' ' &&
           input[i] != '\t' &&
           input[i] != '\n')
        {
            exp[j++] = input[i];
        }
    }

    exp[j] = '\0';
    len = strlen(exp);

    while(ptr < len)
    {
        stack[++top] = exp[ptr++];
        printf("Shift: ");
        printStack();

        reduce();
    }

    reduce();

    if(top == 0 && stack[0] == 'E')
        printf("String Accepted\n");
    else
        printf("String Rejected\n");

    return 0;
}