// Shift Reduce Parser Improved
#include <stdio.h>
#include <string.h>
#include <ctype.h>

// Stack to hold tokens and non-terminals during parsing
char stack[100][10];
int top = -1;      // Points to the top of the stack
int pos = 0;       // Input pointer
char input[100];   // Holds input string

// Push a symbol onto stack
void push(const char *s)
{
    strcpy(stack[++top], s);
}

// Pop top element
void pop()
{
    top--;
}

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

// Apply reduce rules
int reduce()
{
    // Rule 1: E -> E + E
    if (top >= 2 &&
        strcmp(stack[top-2], "E") == 0 &&
        strcmp(stack[top-1], "+") == 0 &&
        strcmp(stack[top], "E") == 0)
    {
        pop();
        pop();
        pop();
        push("E");
        return 1;
    }

    // Rule 2: E -> E * E
    if (top >= 2 &&
        strcmp(stack[top-2], "E") == 0 &&
        strcmp(stack[top-1], "*") == 0 &&
        strcmp(stack[top], "E") == 0)
    {
        pop();
        pop();
        pop();
        push("E");
        return 1;
    }

    // Rule 3: E -> (E)
    if (top >= 2 &&
        strcmp(stack[top-2], "(") == 0 &&
        strcmp(stack[top-1], "E") == 0 &&
        strcmp(stack[top], ")") == 0)
    {
        pop();
        pop();
        pop();
        push("E");
        return 1;
    }

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

    return 0;
}

int main()
{
    printf("Enter an Expression:\n");
    fgets(input, 100, stdin);

    while (input[pos])
    {
        // Ignore spaces
        if (isspace(input[pos]))
        {
            pos++;
            continue;
        }

        char temp[2] = {input[pos], '\0'};
        push(temp);
        pos++;

        printf("Shift: ");
        printStack();

        while (reduce())
        {
            printf("Reduce: ");
            printStack();
        }
    }

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

    return 0;
}