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

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

void push(char c) {
    stack[++top] = c;
    stack[top + 1] = '\0';
}

void reduce() {
    // E -> id
    if (top >= 0 && isalpha(stack[top])) {
        stack[top] = 'E';
        printf("Reduce: E -> id\n");
    }

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

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

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

int main() {
    printf("Enter Expression: ");
    
    scanf(" %[^\n]", input); // بدل fgets

    for (int i = 0; input[i] != '\0'; i++) {

        if (input[i] == ' ')
            continue;

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

        reduce();
    }

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

    return 0;
}