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

char stack[100][10];
int top = -1;
int cursor = 0;
char buffer[100];

void push(const char *symbol) {
    strcpy(stack[++top], symbol);
}

void pop() {
    if (top >= 0) top--;
}

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

int try_reduce() {
    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;
    }

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

    if (top != -1 && islower(stack[top][0]) && strlen(stack[top]) == 1) {
        pop();
        push("E");
        return 1;
    }

    return 0;
}

int main() {
    printf("Enter an Expression: ");
    fgets(buffer, sizeof(buffer), stdin);
    buffer[strcspn(buffer, "\n")] = 0;

    while (buffer[cursor] != '\0') {
        if (isspace(buffer[cursor])) {
            cursor++;
            continue;
        }

        char current[2] = {buffer[cursor], '\0'};
        push(current);
        cursor++;

        printf("Shift: ");
        show_stack();

        while (try_reduce()) {
            printf("Reduce: ");
            show_stack();
        }
    }

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

    return 0;
}