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