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++)
  23.         printf("%s", stack[i]);
  24.     printf("\n");
  25. }
  26.  
  27. int reduce(char lookahead)
  28. {
  29.     if (top >= 0 &&
  30.         stack[top][0] >= 'a' &&
  31.         stack[top][0] <= 'z')
  32.     {
  33.         pop();
  34.         push("F");
  35.         return 1;
  36.     }
  37.  
  38.     if (top >= 2 &&
  39.         strcmp(stack[top-2], "(") == 0 &&
  40.         strcmp(stack[top-1], "E") == 0 &&
  41.         strcmp(stack[top], ")") == 0)
  42.     {
  43.         pop(); pop(); pop();
  44.         push("F");
  45.         return 1;
  46.     }
  47.  
  48.     if (top >= 2 &&
  49.         strcmp(stack[top-2], "T") == 0 &&
  50.         strcmp(stack[top-1], "*") == 0 &&
  51.         strcmp(stack[top], "F") == 0)
  52.     {
  53.         pop(); pop(); pop();
  54.         push("T");
  55.         return 1;
  56.     }
  57.  
  58.     if (top >= 0 &&
  59.         strcmp(stack[top], "F") == 0)
  60.     {
  61.         if (lookahead == '*') return 0;
  62.         pop();
  63.         push("T");
  64.         return 1;
  65.     }
  66.  
  67.     if (top >= 2 &&
  68.         strcmp(stack[top-2], "E") == 0 &&
  69.         strcmp(stack[top-1], "+") == 0 &&
  70.         strcmp(stack[top], "T") == 0)
  71.     {
  72.         if (lookahead == '*') return 0;
  73.         pop(); pop(); pop();
  74.         push("E");
  75.         return 1;
  76.     }
  77.  
  78.     if (top >= 0 &&
  79.         strcmp(stack[top], "T") == 0)
  80.     {
  81.         if (lookahead == '+' || lookahead == '*') return 0;
  82.         pop();
  83.         push("E");
  84.         return 1;
  85.     }
  86.  
  87.     return 0;
  88. }
  89.  
  90. int main()
  91. {
  92.     printf("Enter an Expression:\n");
  93.     fgets(input, 100, stdin);
  94.  
  95.     while (input[pos])
  96.     {
  97.         if (isspace(input[pos]))
  98.         {
  99.             pos++;
  100.             continue;
  101.         }
  102.  
  103.         char temp[2] = {input[pos], '\0'};
  104.         push(temp);
  105.         pos++;
  106.  
  107.         printf("Shift: ");
  108.         printStack();
  109.  
  110.         while (reduce(input[pos]))
  111.         {
  112.             printf("Reduce: ");
  113.             printStack();
  114.         }
  115.     }
  116.  
  117.     while (reduce('\0'))
  118.     {
  119.         printf("Reduce: ");
  120.         printStack();
  121.     }
  122.  
  123.     if (top == 0 && strcmp(stack[0], "E") == 0)
  124.         printf("String Accepted\n");
  125.     else
  126.         printf("String Rejected\n");
  127.  
  128.     return 0;
  129. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
(a + b)
stdout
copy 
Enter an Expression:
Shift: (
Shift: (a
Reduce: (F
Reduce: (T
Reduce: (E
Shift: (E+
Shift: (E+b
Reduce: (E+F
Reduce: (E+T
Reduce: (E
Shift: (E)
Reduce: F
Reduce: T
Reduce: E
String Accepted
https://ideone.com/FrCV5g
language:
C (gcc 8.3)
created:
15 hours 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!