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