#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 100

char stack[MAX][20]; 
int top = -1;      


void push(const char *sym)
{
    top++;
    strcpy(stack[top], sym);
}

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

// Print current stack state
void printStack(const char *action)
{
    printf("%s: ", action);
    for (int i = 0; i <= top; i++)
        printf("%s ", stack[i]);
    printf("\n");
}

int tryReduce()
{
    if (top >= 2 &&
        strcmp(stack[top - 2], "(") == 0 &&
        strcmp(stack[top - 1], "E") == 0 &&
        strcmp(stack[top],     ")") == 0)
    {
        pop(); pop(); pop();        
        push("E");                    
        printStack("Reduce");
        return 1;
    }
    
    if (top >= 2 &&
        strcmp(stack[top - 2], "E") == 0 &&
        strcmp(stack[top - 1], "*") == 0 &&
        strcmp(stack[top],     "E") == 0)
    {
        pop(); pop(); pop();
        push("E");
        printStack("Reduce");
        return 1;
    }

    if (top >= 2 &&
        strcmp(stack[top - 2], "E") == 0 &&
        strcmp(stack[top - 1], "+") == 0 &&
        strcmp(stack[top],     "E") == 0)
    {
        pop(); pop(); pop();
        push("E");
        printStack("Reduce");
        return 1;
    }

    // Rule: E -> id
    // Top is an identifier (not a special symbol)
    if (top >= 0 &&
        strcmp(stack[top], "E") != 0 &&
        strcmp(stack[top], "+") != 0 &&
        strcmp(stack[top], "*") != 0 &&
        strcmp(stack[top], "(") != 0 &&
        strcmp(stack[top], ")") != 0)
    {
        pop();
        push("E");
        printStack("Reduce");
        return 1;
    }

    return 0; // No reduction possible
}

int nextToken(const char *input, int *pos, char *out)
{
    int len = strlen(input);

    // Skip whitespace
    while (*pos < len && isspace((unsigned char)input[*pos]))
        (*pos)++;

    if (*pos >= len) return 0; // No more tokens

    char ch = input[*pos];

    // Single-character tokens: operators and parentheses
    if (ch == '+' || ch == '*' || ch == '(' || ch == ')')
    {
        out[0] = ch;
        out[1] = '\0';
        (*pos)++;
        return 1;
    }
    
    if (isalpha((unsigned char)ch) || ch == '_')
    {
        int start = *pos;
        while (*pos < len && (isalnum((unsigned char)input[*pos]) || input[*pos] == '_'))
            (*pos)++;
        int tlen = *pos - start;
        strncpy(out, input + start, tlen);
        out[tlen] = '\0';
        return 1;
    }

    (*pos)++;
    return 0;
}

void shiftReduceParse(const char *input)
{
    top = -1; 

    int pos = 0;
    char token[50];

    while (nextToken(input, &pos, token))
    {
        push(token);
        printStack("Shift");

        while (tryReduce());
    }

    while (tryReduce());

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

int main()
{
    char input[200];
    printf("Enter an Expression:\n");
    fgets(input, 200, stdin);

    int len = strlen(input);
    if (len > 0 && input[len - 1] == '\n')
        input[len - 1] = '\0';

    shiftReduceParse(input);

    return 0;
}