// Simple Shift Reduce parsing for E → E + E | E * E | (E) | id
#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 i = 0; // Input pointer/index
char input[100]; // Holds the input string (e.g., "a + b * c")
 
// Push a symbol (token or non-terminal) onto the stack
void push(const char *s)
{
    strcpy(stack[++top], s);
}
 
// Pop the top of the stack
void pop()
{
    top--;
}
 
// Print current stack contents
void printStack()
{
    for (int i = 0; i <= top; i++) printf("%s", stack[i]);
    printf("\n");
}
 
// Try to apply a reduction rule to the top of the stack
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()
{
    strcpy(input, "( a +      (b*a))");
 
    // Main parsing loop
    while (input[i])
    {
        // Ignore whitespaces
        if (isspace(input[i])) {
            i++;
            continue;
        }
 
        // SHIFT step
        char temp[2] = {input[i], '\0'};
        push(temp);
        i++;
 
        printf("Shift: ");
        printStack();
 
        // REDUCE step
        while (reduce())
        {
            printf("Reduce: ");
            printStack();
        }
    }
 
    // Final check
    if (top == 0 && strcmp(stack[0], "E")==0)
        printf("String Accepted\n");
    else
        printf("String Rejected\n");
 
    return 0;
}