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

char stack[100][10];
int top = -1;
int pos = 0;   
char input[100];


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


void pop()
{
    top--;
}


void printStack()
{
    for (int i = 0; i <= top; i++)
        printf("%s", stack[i]);
    printf("\n");
}

// Reduce
int reduce()
{
       if (top != -1 && islower(stack[top][0]))
    {
        pop();
        push("E");
        return 1;
    }

 
    if (top >= 2 &&
        strcmp(stack[top - 2], "(") == 0 &&
        strcmp(stack[top - 1], "E") == 0 &&
        strcmp(stack[top], ")") == 0)
    {
        pop(); pop(); pop();
        push("E");
        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");
        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");
        return 1;
    }

    return 0;
}

int main()
{
    
    fgets(input, sizeof(input), stdin);

    while (input[pos])
    {
        
        if (input[pos] == ' ' || input[pos] == '\n')
        {
            pos++;
            continue;
        }

        // SHIFT
        char temp[2] = { input[pos], '\0' };
        push(temp);
        pos++;

        printf("Shift: ");
        printStack();

        // REDUCE
        while (reduce())
        {
            printf("Reduce: ");
            printStack();
        }
    }

    
    while (reduce())
    {
        printf("Reduce: ");
        printStack();
    }

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

    return 0;
}