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

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

void push(const char *s) { strcpy(stack[++top], s); }
void pop(int n) { top -= n; }

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

int reduce() {
    int reduced = 0, again = 1;
    while (again) {
        again = 0;
        // Rule: E -> id
        if (top >= 0 && isalpha(stack[top][0]) && strcmp(stack[top], "E") != 0) {
            printf("  Reduce  id  → E   (token: %s)\n", stack[top]);
            pop(1); push("E");
            again = reduced = 1;
        }
        // Rule: E -> ( E )
        else if (top >= 2 && !strcmp(stack[top-2], "(") && !strcmp(stack[top-1], "E") && !strcmp(stack[top], ")")) {
            printf("  Reduce  ( E ) → E\n");
            pop(3); push("E");
            again = reduced = 1;
        }
        // Rule: E -> E * E
        else if (top >= 2 && !strcmp(stack[top-2], "E") && !strcmp(stack[top-1], "*") && !strcmp(stack[top], "E")) {
            printf("  Reduce  E * E → E\n");
            pop(3); push("E");
            again = reduced = 1;
        }
        // Rule: E -> E + E
        else if (top >= 2 && !strcmp(stack[top-2], "E") && !strcmp(stack[top-1], "+") && !strcmp(stack[top], "E")) {
            printf("  Reduce  E + E → E\n");
            pop(3); push("E");
            again = reduced = 1;
        }
    }
    return reduced;
}

int main() {
    char input[200], tok[20];
    printf("Enter expression: ");
    if (!fgets(input, sizeof(input), stdin)) return 1;

    for (int i = 0; input[i]; ) {
        while (isspace(input[i])) i++;
        if (!input[i]) break;

        int j = 0;
        if (isalpha(input[i]) || input[i] == '_') {
            while (isalnum(input[i]) || input[i] == '_') tok[j++] = input[i++];
        } else {
            tok[j++] = input[i++];
        }
        tok[j] = '\0';

        if (!isalpha(tok[0]) && !strchr("_()+*", tok[0])) {
            printf("  Unknown token '%s' — rejected.\nString Rejected\n", tok);
            return 0;
        }

        printf("Shift  '%s'\n", tok);
        push(tok);
        printStack();
        reduce();
        printStack();
    }

    while (reduce()) printStack();

    if (top == 0 && !strcmp(stack[0], "E"))
        printf("\nString Accepted ✓\n");
    else {
        printf("\nString Rejected ✗  (stack has %d item(s))\n", top + 1);
        printStack();
    }
    return 0;
}