fork download
copy 
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include <string.h>
  4.  
  5. char stack[100];
  6. int top = -1;
  7. char input[100];
  8. int i = 0;
  9.  
  10. void printStack()
  11. {
  12.   for (int j = 0; j <= top; j++)
  13.     printf("%c", stack[j]);
  14.   printf("\n");
  15. }
  16.  
  17. void push(char c)
  18. {
  19.   stack[++top] = c;
  20. }
  21.  
  22. void pop()
  23. {
  24.   if (top >= 0)
  25.     top--;
  26. }
  27.  
  28. int tryReduce()
  29. {
  30.   // Rule: E → (E)
  31.   if (top >= 2 &&
  32.       stack[top] == ')' &&
  33.       stack[top - 1] == 'E' &&
  34.       stack[top - 2] == '(')
  35.   {
  36.     top -= 3;
  37.     push('E');
  38.     return 1;
  39.   }
  40.  
  41.   // Rule: E → E*E
  42.   if (top >= 2 &&
  43.       stack[top] == 'E' &&
  44.       stack[top - 1] == '*' &&
  45.       stack[top - 2] == 'E')
  46.   {
  47.     top -= 3;
  48.     push('E');
  49.     return 1;
  50.   }
  51.  
  52.   // Rule: E → E+E
  53.   if (top >= 2 &&
  54.       stack[top] == 'E' &&
  55.       stack[top - 1] == '+' &&
  56.       stack[top - 2] == 'E')
  57.   {
  58.     top -= 3;
  59.     push('E');
  60.     return 1;
  61.   }
  62.  
  63.   // Rule: E → id
  64.   if (top >= 0 && stack[top] >= 'a' && stack[top] <= 'z')
  65.   {
  66.     pop();
  67.     push('E');
  68.     return 1;
  69.   }
  70.  
  71.   return 0;
  72. }
  73.  
  74. int main()
  75. {
  76.   printf("Enter an expression: ");
  77.   fgets(input, sizeof(input), stdin);
  78.  
  79.   while (input[i])
  80.   {
  81.     if (isspace(input[i]))
  82.     {
  83.       i++;
  84.       continue;
  85.     }
  86.     push(input[i]);
  87.     i++;
  88.     printf("Shift: ");
  89.     printStack();
  90.     while (tryReduce())
  91.     {
  92.       printf("Reduce: ");
  93.       printStack();
  94.     }
  95.   }
  96.   if (top == 0 && stack[0] == 'E')
  97.     printf("String Accepted\n");
  98.   else
  99.     printf("String Rejected\n");
  100.  
  101.   return 0;
  102. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
a +(b*a )
stdout
copy 
Enter an expression: 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
String Accepted
https://ideone.com/la2mzt
language:
C (gcc 8.3)
created:
58 minutes 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!