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

// =====================================================================
//  Shift-Reduce Parser
//  Grammar:
//    E -> E + E
//    E -> E * E
//    E -> id
//    E -> (E)
// =====================================================================

#define MAX 100

char stack[MAX][20]; // The parser stack (each cell = a symbol like "E", "+", "id", etc.)
int top = -1;        // Stack pointer

// ---------- Stack helpers ----------

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");
}

// ---------- Reduce rules ----------
// Try to reduce the top of the stack using grammar rules.
// Returns 1 if a reduction was made, 0 otherwise.

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

    // Rule: E -> E * E
    // Stack top-2 = "E", top-1 = "*", top = "E"
    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 -> E + E
    // Stack top-2 = "E", top-1 = "+", top = "E"
    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
}

// ---------- Tokenizer (get next token, skip whitespace) ----------
// Returns the next token from input starting at position *pos.
// Tokens: "(", ")", "+", "*", or an identifier string.
// Returns 0 if no more tokens, 1 if a token was written into `out`.

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;
    }

    // Identifier: letters and digits
    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;
    }

    // Unknown character — skip it
    (*pos)++;
    return 0;
}

// ---------- Main parser ----------

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

    int pos = 0;
    char token[50];

    while (nextToken(input, &pos, token))
    {
        // SHIFT: push the current token onto the stack
        push(token);
        printStack("Shift");

        // After each shift, try to reduce as many times as possible
        while (tryReduce());
    }

    // After all input consumed, try one final round of reductions
    while (tryReduce());

    // Check if parse succeeded (stack should contain exactly one "E")
    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);

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

    shiftReduceParse(input);

    return 0;
}