// Simple Shift Reduce parsing for E → E + E | id
#include <stdio.h>
#include <string.h>
#include <ctype.h>
// Stack to hold tokens and non-terminals during parsing
char stack[100][10];
int top = -1;      // Points to the top of the stack
int indx = 0;        // Input pointer/index
char input[100];   // Holds the input string (e.g., "a+b+c")

// Push a symbol (token or non-terminal) onto the stack
void push(const char *s)
{
    strcpy(stack[++top], s);
}
// Pop the top of the stack
void pop()
{
    top--;
}
// Print current stack contents
void printStack()
{
    for (int i = 0; i <= top; i++) printf("%s", stack[i]);
    printf("\n");
}


// Try to apply a reduction rule to the  top of the stack
int reduce()
{
    // Rule 1: E → E + E
    if (top >= 2 &&
            strcmp(stack[top-2], "E")==0 &&
            strcmp(stack[top-1], "+")==0 &&
            strcmp(stack[top], "E")==0)
    {
        pop();
        pop();
        pop();   // Remove "E + E" (3 pops)
        push("E");           // Push "E" onto the stack
        return 1;               // Indicate that a reduction occurred
    }
    
    if (top >= 2 &&
            strcmp(stack[top-2], "E")==0 &&
            strcmp(stack[top-1], "*")==0 &&
            strcmp(stack[top], "E")==0)
    {
        pop();
        pop();
        pop();
        push("E");
        return 1;
    } 
    
    if (top>=2
    && strcmp(stack[top],")")==0
    && strcmp(stack[top-1],"E")==0
    && strcmp(stack[top-2],"(")==0 )
    {
        pop();
        pop();
        pop();
        push("E");
        return 1;
    }

    // Rule 2: E → id
    if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
    {
        pop();  // Remove "id" (1 pop)
        push("E");  // Push "E" onto the stack
        return 1;
    }

    return 0; // No reduction matched
}

int main()
{
    
    fgets(input,100,stdin); 
    input[strcspn(input,"\n")]=0;
    
    while (input[indx])
    {
        
        if(input[indx]==' ')
        {
            indx++;
            continue ;
        
        }
        char temp[2] = {input[indx], '\0'};  // turn character into string
        
        push(temp);                           // push actual character (like 'x')
        indx ++;        // Move input pointer ahead by 1

        // Print stack after shift
        printf("Shift: ");
        printStack();


        // REDUCE step: apply all possible reductions after shift
        while (reduce())
        {
            printf("Reduce: ");
            printStack();

        }
    }

    // Final check: input is accepted if the stack has a single symbol "E"
    if (top == 0 && strcmp(stack[0], "E")==0)
        printf("String Accepted\n");
    else
        printf("String Rejected\n");

    return 0;
}