#include <stdio.h>
#include <string.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]);
        if (i < top) printf(" ");
    }
    printf("\n");
}


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

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

    
    if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
    {
        pop();  
        push("E");  
        return 1;
    }

    return 0; 
}

int main()
{
    
    printf("Enter an Expression:\n");
    
    
    fgets(input, sizeof(input), stdin);
    
    
    int len = strlen(input);
    if (len > 0 && input[len-1] == '\n') {
        input[len-1] = '\0';
    }

    
    pos = 0;
    while (input[pos])
    {
        
        while (input[pos] == ' ' || input[pos] == '\t') {
            pos++;
        }
        
        if (!input[pos]) break;  
        
        
        char temp[2] = {input[pos], '\0'};
        push(temp);
        pos++;        

        
        printf("Shift: ");
        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;
}