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

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

// Function to push a character onto the stack
void push(char c) {
    stack[++top] = c;
}

// Function to print the current contents of the stack
void printStack() {
    for (int i = 0; i <= top; i++)
        printf("%c", stack[i]);
}

// Function to apply rules (Shift-Reduce Parsing)
void reduce() {

    // Rule 1: id -> E
    // If top of stack is 'a' or 'b', treat it as identifier (id)
    if (top >= 0 && (stack[top] == 'a' || stack[top] == 'b')) {
        printf("Reduce: id -> E\n");
        stack[top] = 'E';  // Replace with non-terminal E
    }

    // Rule 2: (E) -> E
    // If pattern "(E)" is found on top of stack
    if (top >= 2 && stack[top] == ')' && stack[top-1] == 'E' && stack[top-2] == '(') {
        printf("Reduce: (E) -> E\n");
        top -= 2;          // Remove '(' and ')'
        stack[top] = 'E';  // Replace with E
    }

    // Rule 3: E * E -> E
    // Handle multiplication
    if (top >= 2 && stack[top] == 'E' && stack[top-1] == '*' && stack[top-2] == 'E') {
        printf("Reduce: E * E -> E\n");
        top -= 2;          // Reduce 3 symbols into 1
        stack[top] = 'E';
    }

    // Rule 4: E + E -> E
    // Handle addition
    if (top >= 2 && stack[top] == 'E' && stack[top-1] == '+' && stack[top-2] == 'E') {
        printf("Reduce: E + E -> E\n");
        top -= 2;          // Reduce 3 symbols into 1
        stack[top] = 'E';
    }
}

int main() {
    char input[100];
    int i = 0;

    printf("Enter an Expression: ");
    fgets(input, sizeof(input), stdin);

    // Remove newline character from input
    input[strcspn(input, "\n")] = '\0';

    printf("\nParsing Steps:\n");

    while (input[i] != '\0') {

        // Skip whitespace
        if (isspace(input[i])) {
            i++;
            continue;
        }

        // SHIFT operation: push character to stack
        printf("Shift: %c\n", input[i]);
        push(input[i]);

        // Print current stack after shift
        printStack();
        printf("\n");

        // Try to REDUCE after shift
        reduce();

        i++;
    }

    // After input ends, try to reduce remaining stack
    while (top > 0) {
        reduce();
    }

    // Final check: if stack contains only 'E', input is accepted
    if (top == 0 && stack[top] == 'E') {
        printf("String Accepted\n");
    } else {
        printf("String Rejected\n");
    }

    return 0;
}