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 index = 0;
  8. char input[100];
  9.  
  10. void push(const char *s) {
  11.     strcpy(stack[++top], s);
  12. }
  13.  
  14. void pop() {
  15.     top--;
  16. }
  17.  
  18. void printStack() {
  19.     for(int i = 0; i <= top; i++) printf("%s", stack[i]);
  20.     printf("\n");
  21. }
  22.  
  23. int reduce() {
  24.     // Rule 1: E -> E + E
  25.     if(top >= 2 &&
  26.        strcmp(stack[top-2], "E") == 0 &&
  27.        strcmp(stack[top-1], "+") == 0 &&
  28.        strcmp(stack[top], "E") == 0) {
  29.         pop(); pop(); pop();
  30.         push("E");
  31.         return 1;
  32.     }
  33.  
  34.     // Rule 2: E -> E * E
  35.     if(top >= 2 &&
  36.        strcmp(stack[top-2], "E") == 0 &&
  37.        strcmp(stack[top-1], "*") == 0 &&
  38.        strcmp(stack[top], "E") == 0) {
  39.         pop(); pop(); pop();
  40.         push("E");
  41.         return 1;
  42.     }
  43.  
  44.     // Rule 3: E -> ( E )
  45.     if(top >= 2 &&
  46.        strcmp(stack[top-2], "(") == 0 &&
  47.        strcmp(stack[top-1], "E") == 0 &&
  48.        strcmp(stack[top], ")") == 0) {
  49.         pop(); pop(); pop();
  50.         push("E");
  51.         return 1;
  52.     }
  53.  
  54.     // Rule 4: E -> id 
  55.     if(top!=-1 && stack[top][0]>= 'a' && stack[top][0] <= 'z') {
  56.         pop();
  57.         push("E");
  58.         return 1;
  59.     }
  60.  
  61.     return 0; // No reduction applied
  62. }
  63.  
  64. int main() {
  65.     fgets(input, sizeof(input), stdin); // allow input with spaces
  66.  
  67.     while(input[index]) {
  68.         if(isspace(input[index])) {
  69.             index++; // skip whitespace
  70.             continue;
  71.         }
  72.  
  73.         char temp[2] = {input[index], '\0'};
  74.         push(temp);
  75.         index++;
  76.  
  77.         printf("Shift: ");
  78.         printStack();
  79.  
  80.         while(reduce()) {
  81.             printf("Reduce: ");
  82.             printStack();
  83.         }
  84.     }
  85.  
  86.     if(top == 0 && strcmp(stack[0], "E") == 0)
  87.         printf("string Accepted\n");
  88.     else
  89.         printf("string Rejected\n");
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
a + ( b * (d+a*c)+g)
stdout
copy 
Shift: a
Reduce: E
Shift: E+
Shift: E+(
Shift: E+(b
Reduce: E+(E
Shift: E+(E*
Shift: E+(E*(
Shift: E+(E*(d
Reduce: E+(E*(E
Shift: E+(E*(E+
Shift: E+(E*(E+a
Reduce: E+(E*(E+E
Reduce: E+(E*(E
Shift: E+(E*(E*
Shift: E+(E*(E*c
Reduce: E+(E*(E*E
Reduce: E+(E*(E
Shift: E+(E*(E)
Reduce: E+(E*E
Reduce: E+(E
Shift: E+(E+
Shift: E+(E+g
Reduce: E+(E+E
Reduce: E+(E
Shift: E+(E)
Reduce: E+E
Reduce: E
string Accepted
https://ideone.com/o8dDn3
language:
C (gcc 8.3)
created:
11 days 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!