#include <stdio.h>
#include <string.h>
#include <ctype.h>
 
// Array functioning as our parsing stack
char p_stack[100][10];
int sp = -1;        // Stack pointer
int cursor = 0;     // Tracks current position in the input string
char expr_str[100]; // Stores the user's expression
 
// Add a token to the top of the stack
void push_sym(const char *val) {
    strcpy(p_stack[++sp], val);
}
 
// Remove the topmost token
void pop_sym() {
    if (sp >= 0) {
        sp--;
    }
}
 
// Output the current state of the stack
void show_stack() {
    for (int k = 0; k <= sp; k++) {
        printf("%s ", p_stack[k]);
    }
    printf("\n");
}
 
// Check if the top of the stack matches any grammar rules
int attempt_reduction() {
    // Rule: E -> ( E )
    if (sp >= 2 &&
        strcmp(p_stack[sp - 2], "(") == 0 &&
        strcmp(p_stack[sp - 1], "E") == 0 &&
        strcmp(p_stack[sp], ")") == 0) {
        pop_sym(); pop_sym(); pop_sym();
        push_sym("E");
        return 1;
    }
 
    // Rule: E -> E + E
    if (sp >= 2 &&
        strcmp(p_stack[sp - 2], "E") == 0 &&
        strcmp(p_stack[sp - 1], "+") == 0 &&
        strcmp(p_stack[sp], "E") == 0) {
        pop_sym(); pop_sym(); pop_sym();
        push_sym("E");
        return 1;
    }
 
    // Rule: E -> E * E
    if (sp >= 2 &&
        strcmp(p_stack[sp - 2], "E") == 0 &&
        strcmp(p_stack[sp - 1], "*") == 0 &&
        strcmp(p_stack[sp], "E") == 0) {
        pop_sym(); pop_sym(); pop_sym();
        push_sym("E");
        return 1;
    }
 
    // Rule: E -> id (any single lowercase char)
    if (sp != -1 && islower(p_stack[sp][0]) && strlen(p_stack[sp]) == 1) {
        pop_sym();
        push_sym("E");
        return 1;
    }
 
    return 0; // No rule matched
}
 
int main() {
    printf("Input an arithmetic expression: ");
    // Read the string including spaces
    fgets(expr_str, sizeof(expr_str), stdin);
 
    // Strip the trailing newline character if it exists
    expr_str[strcspn(expr_str, "\n")] = 0;
 
    while (expr_str[cursor] != '\0') {
        // 1. Skip over any whitespaces
        if (isspace(expr_str[cursor])) {
            cursor++;
            continue;
        }
 
        // 2. Perform SHIFT operation
        char sym_buf[2] = {expr_str[cursor], '\0'};
        push_sym(sym_buf);
        cursor++;
 
        printf("Action [Shift]:  ");
        show_stack();
 
        // 3. Perform REDUCE operation as long as rules match
        while (attempt_reduction()) {
            printf("Action [Reduce]: ");
            show_stack();
        }
    }
 
    // Final validation: Stack should contain only 'E'
    if (sp == 0 && strcmp(p_stack[0], "E") == 0) {
        printf("Result: String Accepted\n");
    } else {
        printf("Result: String Rejected\n");
    }
 
    return 0;
}