fork(1) 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 ind = 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++)
  23.         printf("%s", stack[i]);
  24.     printf("\n");
  25. }
  26.  
  27. int reduce()
  28. {
  29.     // E → E + E
  30.     if (top >= 2 &&
  31.         strcmp(stack[top-2], "E")==0 &&
  32.         strcmp(stack[top-1], "+")==0 &&
  33.         strcmp(stack[top], "E")==0)
  34.     {
  35.         pop(); pop(); pop();
  36.         push("E");
  37.         return 1;
  38.     }
  39.  
  40.     // E → E * E
  41.     if (top >= 2 &&
  42.         strcmp(stack[top-2], "E")==0 &&
  43.         strcmp(stack[top-1], "*")==0 &&
  44.         strcmp(stack[top], "E")==0)
  45.     {
  46.         pop(); pop(); pop();
  47.         push("E");
  48.         return 1;
  49.     }
  50.  
  51.     // E → (E)
  52.     if (top >= 2 &&
  53.         strcmp(stack[top-2], "(")==0 &&
  54.         strcmp(stack[top-1], "E")==0 &&
  55.         strcmp(stack[top], ")")==0)
  56.     {
  57.         pop(); pop(); pop();
  58.         push("E");
  59.         return 1;
  60.     }
  61.  
  62.     // E → id (fix infinite loop)
  63.     if (top != -1 &&
  64.         isalpha(stack[top][0]) &&
  65.         strcmp(stack[top], "E") != 0)
  66.     {
  67.         pop();
  68.         push("E");
  69.         return 1;
  70.     }
  71.  
  72.     return 0;
  73. }
  74.  
  75. int main()
  76. {
  77.     printf("Enter an Expression: ");
  78.     fgets(input, sizeof(input), stdin);
  79.  
  80.     while (input[ind])
  81.     {
  82.         // ignore spaces
  83.  
  84.         if (isspace(input[ind]))
  85.         {
  86.             ind++;
  87.             continue;
  88.         }
  89.  
  90.         char temp[2] = {input[ind], '\0'};
  91.         push(temp);
  92.         ind++;
  93.  
  94.         printf("Shift: ");
  95.         printStack();
  96.  
  97.         while (reduce())
  98.         {
  99.             printf("Reduce: ");
  100.             printStack();
  101.         }
  102.     }
  103.  
  104.     if (top == 0 && strcmp(stack[0], "E")==0)
  105.         printf("String Accepted\n");
  106.     else
  107.         printf("String Rejected\n");
  108.  
  109.     return 0;
  110. }
  111.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
a + b * c
stdout
copy 
Enter an Expression: Shift: a
Reduce: E
Shift: E+
Shift: E+b
Reduce: E+E
Reduce: E
Shift: E*
Shift: E*c
Reduce: E*E
Reduce: E
String Accepted
https://ideone.com/2MYvuI
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!