fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5. #define MAX 100
  6.  
  7. char input[MAX];
  8. char stack[MAX];
  9. int top = -1;
  10. int inputIndex = 0;
  11.  
  12. void push(char c)
  13. {
  14.     stack[++top] = c;
  15.     stack[top + 1] = '\0';
  16. }
  17.  
  18. void printState(const char *action)
  19. {
  20.     printf("%-15s Stack: %-20s Input: %s\n", action, stack, input + inputIndex);
  21. }
  22.  
  23. int reduce()
  24. {
  25.     if (top >= 0 && isalpha(stack[top]) && stack[top] != 'E')
  26.     {
  27.         stack[top] = 'E';
  28.         printState("Reduce id->E");
  29.         return 1;
  30.     }
  31.  
  32.     if (top >= 2 &&
  33.         stack[top] == ')' &&
  34.         stack[top - 1] == 'E' &&
  35.         stack[top - 2] == '(')
  36.     {
  37.         stack[top - 2] = 'E';
  38.         top -= 2;
  39.         stack[top + 1] = '\0';
  40.         printState("Reduce (E)->E");
  41.         return 1;
  42.     }
  43.  
  44.     if (top >= 2 &&
  45.         stack[top] == 'E' &&
  46.         stack[top - 1] == '*' &&
  47.         stack[top - 2] == 'E')
  48.     {
  49.         stack[top - 2] = 'E';
  50.         top -= 2;
  51.         stack[top + 1] = '\0';
  52.         printState("Reduce E*E->E");
  53.         return 1;
  54.     }
  55.  
  56.     if (top >= 2 &&
  57.         stack[top] == 'E' &&
  58.         stack[top - 1] == '+' &&
  59.         stack[top - 2] == 'E')
  60.     {
  61.         stack[top - 2] = 'E';
  62.         top -= 2;
  63.         stack[top + 1] = '\0';
  64.         printState("Reduce E+E->E");
  65.         return 1;
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  
  71. void parse()
  72. {
  73.     while (input[inputIndex] != '\0')
  74.     {
  75.         if (isspace(input[inputIndex]))
  76.         {
  77.             inputIndex++;
  78.             continue;
  79.         }
  80.  
  81.         push(input[inputIndex]);
  82.         printState("Shift");
  83.         inputIndex++;
  84.  
  85.         while (reduce());
  86.     }
  87.  
  88.     while (reduce());
  89.  
  90.     if (top == 0 && stack[0] == 'E')
  91.         printf("\nString Accepted\n");
  92.     else
  93.         printf("\nString Rejected\n");
  94. }
  95.  
  96. int main()
  97. {
  98.     printf("Enter expression: ");
  99.     fgets(input, sizeof(input), stdin);
  100.  
  101.     input[strcspn(input, "\n")] = '\0';
  102.  
  103.     stack[0] = '\0';
  104.  
  105.     parse();
  106.  
  107.     return 0;
  108. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
a * (b +a)
stdout
copy 
Enter expression: Shift           Stack: a                    Input: a * (b +a)
Reduce id->E    Stack: E                    Input:  * (b +a)
Shift           Stack: E*                   Input: * (b +a)
Shift           Stack: E*(                  Input: (b +a)
Shift           Stack: E*(b                 Input: b +a)
Reduce id->E    Stack: E*(E                 Input:  +a)
Shift           Stack: E*(E+                Input: +a)
Shift           Stack: E*(E+a               Input: a)
Reduce id->E    Stack: E*(E+E               Input: )
Reduce E+E->E   Stack: E*(E                 Input: )
Shift           Stack: E*(E)                Input: )
Reduce (E)->E   Stack: E*E                  Input: 
Reduce E*E->E   Stack: E                    Input: 

String Accepted
https://ideone.com/pXOg95
language:
C (gcc 8.3)
created:
1 hour 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!