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

#define MAX 100

char input[MAX];
char stack[MAX];
int top = -1;
int inputIndex = 0;

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

void printState(const char *action)
{
    printf("%-15s Stack: %-20s Input: %s\n", action, stack, input + inputIndex);
}

int reduce()
{
    if (top >= 0 && isalpha(stack[top]) && stack[top] != 'E')
    {
        stack[top] = 'E';
        printState("Reduce id->E");
        return 1;
    }

    if (top >= 2 &&
        stack[top] == ')' &&
        stack[top - 1] == 'E' &&
        stack[top - 2] == '(')
    {
        stack[top - 2] = 'E';
        top -= 2;
        stack[top + 1] = '\0';
        printState("Reduce (E)->E");
        return 1;
    }

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

    if (top >= 2 &&
        stack[top] == 'E' &&
        stack[top - 1] == '+' &&
        stack[top - 2] == 'E')
    {
        stack[top - 2] = 'E';
        top -= 2;
        stack[top + 1] = '\0';
        printState("Reduce E+E->E");
        return 1;
    }

    return 0;
}

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

        push(input[inputIndex]);
        printState("Shift");
        inputIndex++;

        while (reduce());
    }

    while (reduce());

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

int main()
{
    printf("Enter expression: ");
    fgets(input, sizeof(input), stdin);

    input[strcspn(input, "\n")] = '\0';

    stack[0] = '\0';

    parse();

    return 0;
}