fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5. char stack[100][10];
  6. int top = -1;
  7. int pos = 0;
  8. char input[100];
  9.  
  10. void push(const char *s)
  11. {
  12.     strcpy(stack[++top], s);
  13. }
  14.  
  15. void pop()
  16. {
  17.     top--;
  18. }
  19.  
  20. void printStack()
  21. {
  22.     for (int i = 0; i <= top; i++) printf("%s", stack[i]);
  23.     printf("\n");
  24. }
  25.  
  26. int reduce()
  27. {
  28.     // Rule 1: E → E + E
  29.     if (top >= 2 &&
  30.             strcmp(stack[top-2], "E")==0 &&
  31.             strcmp(stack[top-1], "+")==0 &&
  32.             strcmp(stack[top], "E")==0)
  33.     {
  34.         pop();
  35.         pop();
  36.         pop();   // Remove "E + E" (3 pops)
  37.         push("E");           // Push "E" onto the stack
  38.         return 1;               // Indicate that a reduction occurred
  39.     }
  40.  
  41.     // Rule 1: E → E * E
  42.     if (top >= 2 &&
  43.             strcmp(stack[top-2], "E")==0 &&
  44.             strcmp(stack[top-1], "*")==0 &&
  45.             strcmp(stack[top], "E")==0)
  46.     {
  47.         pop();
  48.         pop();
  49.         pop();   // Remove "E * E" (3 pops)
  50.         push("E");           // Push "E" onto the stack
  51.         return 1;               // Indicate that a reduction occurred
  52.     }
  53.  
  54.     // Rule 1: E → (E)
  55.     if (top >= 2 &&
  56.             strcmp(stack[top-2], "(")==0 &&
  57.             strcmp(stack[top-1], "E")==0 &&
  58.             strcmp(stack[top], ")")==0)
  59.     {
  60.         pop();
  61.         pop();
  62.         pop();   // Remove "(E)" (3 pops)
  63.         push("E");           // Push "E" onto the stack
  64.         return 1;               // Indicate that a reduction occurred
  65.     }
  66.  
  67.     // Rule 2: E → id
  68.     if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
  69.     {
  70.         pop();  // Remove "id" (1 pop)
  71.         push("E");  // Push "E" onto the stack
  72.         return 1;
  73.     }
  74.  
  75.     return 0;
  76. }
  77.  
  78. int main()
  79. {
  80.     fgets(input, sizeof(input), stdin);
  81.     printf("===============================\n");
  82.  
  83.     size_t len = strlen(input);
  84.  
  85.     if (len > 0 && input[len - 1] == '\n') {
  86.         input[len - 1] = '\0';
  87.     }
  88.  
  89.     while (input[pos])
  90.     {
  91.  
  92.         if (input[pos] == ' ' || input[pos] == '\0'){
  93.             pos ++;
  94.             continue;
  95.         }
  96.  
  97.         char temp[2] = {input[pos], '\0'};
  98.         push(temp);
  99.         pos ++; 
  100.  
  101.         printf("Shift: ");
  102.         printStack();
  103.  
  104.         while (reduce())
  105.         {
  106.             printf("Reduce: ");
  107.             printStack();
  108.  
  109.         }
  110.     }
  111.  
  112.     // Final check: input is accepted if the stack has a single symbol "E"
  113.     if (top == 0 && strcmp(stack[0], "E")==0){
  114.         printf("===============================\n");
  115.         printf("String Accepted\n");
  116.         printf("===============================");
  117.     }
  118.     else{
  119.         printf("===============================\n");
  120.         printf("String Rejected\n");
  121.         printf("===============================");
  122.     }
  123.  
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
(a+(b*a))
stdout
copy 
===============================
Shift: (
Shift: (a
Reduce: (E
Shift: (E+
Shift: (E+(
Shift: (E+(b
Reduce: (E+(E
Shift: (E+(E*
Shift: (E+(E*a
Reduce: (E+(E*E
Reduce: (E+(E
Shift: (E+(E)
Reduce: (E+E
Reduce: (E
Shift: (E)
Reduce: E
===============================
String Accepted
===============================
https://ideone.com/1a4W7P
language:
C (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!