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

char stack[100][10];
int top = -1;
int pos = 0;
char input[100];

void push(const char *s) {
    if (top < 99)
        strcpy(stack[++top], s);
    else
        printf("Stack overflow!\n");
}

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

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

void skipWhitespace() {
    while (input[pos] == ' ') pos++;
}

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

    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;
    }

    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 >= 0 && islower(stack[top][0]) && stack[top][1] == '\0') {
        pop();
        push("E");
        return 1;
    }

    return 0;
}

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

    while (input[pos] != '\0') {
        skipWhitespace();
        if (input[pos] == '\0') break;

        char temp[2] = {input[pos], '\0'};

        if (islower(input[pos]) || input[pos] == '+' || input[pos] == '*' || input[pos] == '(' || input[pos] == ')') {
            push(temp);
            pos++;

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

            while (reduce()) {
                printf("Reduce: ");
                printStack();
            }
        } else {
            printf("Invalid character: %c\n", input[pos]);
            return 1;
        }
    }

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

    return 0;
}