// Simple Shift Reduce parsing for E → E + E | 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 index = 0;     // Input pointer/index
char input[100];   // Holds the input string (e.g., "a + b * (c + d)")
 
// 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();
        push("E");
        return 1;
    }
    
    // Rule 2: E → id
    if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
    {
        pop(); 
        push("E");  
        return 1;
    }
 
    // Rule 3: 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();
        push("E");
        return 1;
    }
 
    // Rule 4: E → (E)
    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;
    }

 
    return 0; // No reduction matched
}
 
int main() {
    // Read input string (e.g., a + b * (c + d))
    fgets(input, sizeof(input), stdin); // يقبل مسافات بيضاء
 
    // Main parsing loop: continue until input ends and no more reductions are possible
    while (input[index]) {
        if (isspace(input[index])) { // تجاهل المسافات
            index++;
            continue;
        }
 
        // SHIFT step: if input is not yet fully consumed
        char temp[2] = {input[index], '\0'};  // turn character into string
        push(temp);                           // push actual character (like 'x')
        index++;        // 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;
}