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

char stack[50], input[50];
int top = -1;
int pos = 0;

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

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

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

void shiftReduce() {
    while (input[pos] != '\0') {
        if (isspace(input[pos])) {
            pos++;
            continue;
        }

        push(input[pos]);
        printf("Shift: ");
        printStack();
        printf("\n");

        if (isalpha(input[pos])) {
            pop();
            push('E');
            printf("Reduce: ");
            printStack();
            printf("\n");
        }
        else if (input[pos] == ')') {
            if (top >= 2 && stack[top-2] == '(' && stack[top-1] == 'E') {
                pop();
                pop();
                pop();
                push('E');
                printf("Reduce: ");
                printStack();
                printf("\n");
            }
        }
        pos++;
    }

    while (top >= 2) {
        if (stack[top] == 'E' && (stack[top-1] == '+' || stack[top-1] == '*') && stack[top-2] == 'E') {
            pop();
            pop();
            pop();
            push('E');
            printf("Reduce: ");
            printStack();
            printf("\n");
        } else {
            break;
        }
    }

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

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