// 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 index1 = 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-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
    }
 
    // 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;
    }
 
    //Rule 3: (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)
    fgets(input, sizeof(input), stdin); //input string must not include white spaces
    input[strcspn(input, "\n")] = '\0';//this one will scan all input untill it reach "\n" then will return index
    // so if input is a + b
    //it will present a + b\n\0
    //in this case strcspn will return 5
    //then input[5]will = "\0"which mean endofstring
 
    //E+a
    // Main parsing loop: continue until input ends and no more reductions are possible
    while (input[index1] != '\0')
    {
        if(input[index1] == ' '){//to ignore white spaces
            index1++;
            continue;
        }
        // SHIFT step: if input is not yet fully consumed
        // Check for "id" token
        char temp[2] = {input[index1], '\0'};  // turn character into string
        push(temp);                           // push actual character (like 'x')
        index1 ++;        // 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;
}

Ly8gU2ltcGxlIFNoaWZ0IFJlZHVjZSBwYXJzaW5nIGZvciBFIOKGkiBFICsgRSB8IGlkCiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDxjdHlwZS5oPgovLyBTdGFjayB0byBob2xkIHRva2VucyBhbmQgbm9uLXRlcm1pbmFscyBkdXJpbmcgcGFyc2luZwpjaGFyIHN0YWNrWzEwMF1bMTBdOwppbnQgdG9wID0gLTE7ICAgICAgLy8gUG9pbnRzIHRvIHRoZSB0b3Agb2YgdGhlIHN0YWNrCmludCBpbmRleDEgPSAwOyAgICAgICAgLy8gSW5wdXQgcG9pbnRlci9pbmRleApjaGFyIGlucHV0WzEwMF07ICAgLy8gSG9sZHMgdGhlIGlucHV0IHN0cmluZyAoZS5nLiwgImErYitjIikKCi8vIFB1c2ggYSBzeW1ib2wgKHRva2VuIG9yIG5vbi10ZXJtaW5hbCkgb250byB0aGUgc3RhY2sKdm9pZCBwdXNoKGNvbnN0IGNoYXIgKnMpCnsKICAgIHN0cmNweShzdGFja1srK3RvcF0sIHMpOwp9Ci8vIFBvcCB0aGUgdG9wIG9mIHRoZSBzdGFjawp2b2lkIHBvcCgpCnsKICAgIHRvcC0tOwp9Ci8vIFByaW50IGN1cnJlbnQgc3RhY2sgY29udGVudHMKdm9pZCBwcmludFN0YWNrKCkKewogICAgZm9yIChpbnQgaSA9IDA7IGkgPD0gdG9wOyBpKyspIHByaW50ZigiJXMiLCBzdGFja1tpXSk7CiAgICBwcmludGYoIlxuIik7Cn0KCgovLyBUcnkgdG8gYXBwbHkgYSByZWR1Y3Rpb24gcnVsZSB0byB0aGUgIHRvcCBvZiB0aGUgc3RhY2sKaW50IHJlZHVjZSgpCnsKICAgIC8vIFJ1bGUgMTogRSDihpIgRSArIEUKICAgIGlmICh0b3AgPj0gMiAmJgogICAgICAgICAgICBzdHJjbXAoc3RhY2tbdG9wLTJdLCAiRSIpPT0wICYmCiAgICAgICAgICAgIChzdHJjbXAoc3RhY2tbdG9wLTFdLCAiKyIpPT0wfHxzdHJjbXAoc3RhY2tbdG9wLTFdLCAiKiIpPT0wKSAmJgogICAgICAgICAgICBzdHJjbXAoc3RhY2tbdG9wXSwgIkUiKT09MCkKICAgIHsKICAgICAgICBwb3AoKTsKICAgICAgICBwb3AoKTsKICAgICAgICBwb3AoKTsgICAvLyBSZW1vdmUgIkUgKyBFIiAoMyBwb3BzKQogICAgICAgIHB1c2goIkUiKTsgICAgICAgICAgIC8vIFB1c2ggIkUiIG9udG8gdGhlIHN0YWNrCiAgICAgICAgcmV0dXJuIDE7ICAgICAgICAgICAgICAgLy8gSW5kaWNhdGUgdGhhdCBhIHJlZHVjdGlvbiBvY2N1cnJlZAogICAgfQoKICAgIC8vIFJ1bGUgMjogRSDihpIgaWQKICAgIGlmICh0b3AhPS0xICYmIHN0YWNrW3RvcF1bMF0+PSdhJyYmc3RhY2tbdG9wXVswXTw9J3onKQogICAgewogICAgICAgIHBvcCgpOyAgLy8gUmVtb3ZlICJpZCIgKDEgcG9wKQogICAgICAgIHB1c2goIkUiKTsgIC8vIFB1c2ggIkUiIG9udG8gdGhlIHN0YWNrCiAgICAgICAgcmV0dXJuIDE7CiAgICB9CiAgICAKICAgIC8vUnVsZSAzOiAoRSkgLT4gRQogICAgaWYodG9wPj0yJiZzdHJjbXAoc3RhY2tbdG9wLTJdLCAiKCIpPT0wJiZzdHJjbXAoc3RhY2tbdG9wLTFdLCAiRSIpPT0wJiZzdHJjbXAoc3RhY2tbdG9wXSwgIikiKT09MCl7CiAgICAgICAgcG9wKCk7CiAgICAgICAgcG9wKCk7CiAgICAgICAgcG9wKCk7CiAgICAgICAgcHVzaCgiRSIpOwogICAgICAgIHJldHVybiAxOwogICAgfQogICAKCiAgICByZXR1cm4gMDsgLy8gTm8gcmVkdWN0aW9uIG1hdGNoZWQKfQoKCmludCBtYWluKCkKewogICAgLy8gUmVhZCBpbnB1dCBzdHJpbmcgKGUuZy4sIGErYitjKQogICAgZmdldHMoaW5wdXQsIHNpemVvZihpbnB1dCksIHN0ZGluKTsgLy9pbnB1dCBzdHJpbmcgbXVzdCBub3QgaW5jbHVkZSB3aGl0ZSBzcGFjZXMKICAgIGlucHV0W3N0cmNzcG4oaW5wdXQsICJcbiIpXSA9ICdcMCc7Ly90aGlzIG9uZSB3aWxsIHNjYW4gYWxsIGlucHV0IHVudGlsbCBpdCByZWFjaCAiXG4iIHRoZW4gd2lsbCByZXR1cm4gaW5kZXgKICAgIC8vIHNvIGlmIGlucHV0IGlzIGEgKyBiCiAgICAvL2l0IHdpbGwgcHJlc2VudCBhICsgYlxuXDAKICAgIC8vaW4gdGhpcyBjYXNlIHN0cmNzcG4gd2lsbCByZXR1cm4gNQogICAgLy90aGVuIGlucHV0WzVdd2lsbCA9ICJcMCJ3aGljaCBtZWFuIGVuZG9mc3RyaW5nCgogICAgLy9FK2EKICAgIC8vIE1haW4gcGFyc2luZyBsb29wOiBjb250aW51ZSB1bnRpbCBpbnB1dCBlbmRzIGFuZCBubyBtb3JlIHJlZHVjdGlvbnMgYXJlIHBvc3NpYmxlCiAgICB3aGlsZSAoaW5wdXRbaW5kZXgxXSAhPSAnXDAnKQogICAgewogICAgICAgIGlmKGlucHV0W2luZGV4MV0gPT0gJyAnKXsvL3RvIGlnbm9yZSB3aGl0ZSBzcGFjZXMKICAgICAgICAgICAgaW5kZXgxKys7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICAvLyBTSElGVCBzdGVwOiBpZiBpbnB1dCBpcyBub3QgeWV0IGZ1bGx5IGNvbnN1bWVkCiAgICAgICAgLy8gQ2hlY2sgZm9yICJpZCIgdG9rZW4KICAgICAgICBjaGFyIHRlbXBbMl0gPSB7aW5wdXRbaW5kZXgxXSwgJ1wwJ307ICAvLyB0dXJuIGNoYXJhY3RlciBpbnRvIHN0cmluZwogICAgICAgIHB1c2godGVtcCk7ICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8gcHVzaCBhY3R1YWwgY2hhcmFjdGVyIChsaWtlICd4JykKICAgICAgICBpbmRleDEgKys7ICAgICAgICAvLyBNb3ZlIGlucHV0IHBvaW50ZXIgYWhlYWQgYnkgMQoKICAgICAgICAvLyBQcmludCBzdGFjayBhZnRlciBzaGlmdAogICAgICAgIHByaW50ZigiU2hpZnQ6ICIpOwogICAgICAgIHByaW50U3RhY2soKTsKCgogICAgICAgIC8vIFJFRFVDRSBzdGVwOiBhcHBseSBhbGwgcG9zc2libGUgcmVkdWN0aW9ucyBhZnRlciBzaGlmdAogICAgICAgIHdoaWxlIChyZWR1Y2UoKSkKICAgICAgICB7CiAgICAgICAgICAgIHByaW50ZigiUmVkdWNlOiAiKTsKICAgICAgICAgICAgcHJpbnRTdGFjaygpOwoKICAgICAgICB9CiAgICB9CgogICAgLy8gRmluYWwgY2hlY2s6IGlucHV0IGlzIGFjY2VwdGVkIGlmIHRoZSBzdGFjayBoYXMgYSBzaW5nbGUgc3ltYm9sICJFIgogICAgaWYgKHRvcCA9PSAwICYmIHN0cmNtcChzdGFja1swXSwgIkUiKT09MCkKICAgICAgICBwcmludGYoIlN0cmluZyBBY2NlcHRlZFxuIik7CiAgICBlbHNlCiAgICAgICAgcHJpbnRmKCJTdHJpbmcgUmVqZWN0ZWRcbiIpOwoKICAgIHJldHVybiAwOwp9