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

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

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

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

int reduce() {

    // id → E 
    if (top >= 0 && (stack[top] >= 'a' && stack[top] <= 'z')) {
        printf("Reduce: id -> E\n");
        stack[top] = 'E';
        return 1;
    }

    // (E) → E
    if (top >= 2 && stack[top] == ')' && stack[top-1] == 'E' && stack[top-2] == '(') {
        printf("Reduce: (E) -> E\n");
        top -= 2;
        stack[top] = 'E';
        return 1;
    }

    // E * E → E
    if (top >= 2 && stack[top] == 'E' && stack[top-1] == '*' && stack[top-2] == 'E') {
        printf("Reduce: E * E -> E\n");
        top -= 2;
        stack[top] = 'E';
        return 1;
    }

    // E + E → E
    if (top >= 2 && stack[top] == 'E' && stack[top-1] == '+' && stack[top-2] == 'E') {
        printf("Reduce: E + E -> E\n");
        top -= 2;
        stack[top] = 'E';
        return 1;
    }

    return 0;
}

int main() {
    char input[100];
    int i = 0;

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

    input[strcspn(input, "\n")] = '\0';

    printf("\nParsing Steps:\n");

    while (input[i] != '\0') {

        if (isspace(input[i])) {
            i++;
            continue;
        }

        printf("Shift: %c\n", input[i]);
        push(input[i]);
        printStack();

        while (reduce()) {
            printStack();
        }

        i++;
    }

    while (reduce()) {
        printStack();
    }

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

    return 0;
}