fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5. char stack[100];
  6. int top = -1;
  7.  
  8. void push(char c) {
  9.     stack[++top] = c;
  10. }
  11.  
  12. void printStack() {
  13.     for (int i = 0; i <= top; i++)
  14.         printf("%c", stack[i]);
  15.     printf("\n");
  16. }
  17.  
  18. int reduce() {
  19.  
  20.     // id → E 
  21.     if (top >= 0 && (stack[top] >= 'a' && stack[top] <= 'z')) {
  22.         printf("Reduce: id -> E\n");
  23.         stack[top] = 'E';
  24.         return 1;
  25.     }
  26.  
  27.     // (E) → E
  28.     if (top >= 2 && stack[top] == ')' && stack[top-1] == 'E' && stack[top-2] == '(') {
  29.         printf("Reduce: (E) -> E\n");
  30.         top -= 2;
  31.         stack[top] = 'E';
  32.         return 1;
  33.     }
  34.  
  35.     // E * E → E
  36.     if (top >= 2 && stack[top] == 'E' && stack[top-1] == '*' && stack[top-2] == 'E') {
  37.         printf("Reduce: E * E -> E\n");
  38.         top -= 2;
  39.         stack[top] = 'E';
  40.         return 1;
  41.     }
  42.  
  43.     // E + E → E
  44.     if (top >= 2 && stack[top] == 'E' && stack[top-1] == '+' && stack[top-2] == 'E') {
  45.         printf("Reduce: E + E -> E\n");
  46.         top -= 2;
  47.         stack[top] = 'E';
  48.         return 1;
  49.     }
  50.  
  51.     return 0;
  52. }
  53.  
  54. int main() {
  55.     char input[100];
  56.     int i = 0;
  57.  
  58.     printf("Enter an Expression: ");
  59.     fgets(input, sizeof(input), stdin);
  60.  
  61.     input[strcspn(input, "\n")] = '\0';
  62.  
  63.     printf("\nParsing Steps:\n");
  64.  
  65.     while (input[i] != '\0') {
  66.  
  67.         if (isspace(input[i])) {
  68.             i++;
  69.             continue;
  70.         }
  71.  
  72.         printf("Shift: %c\n", input[i]);
  73.         push(input[i]);
  74.         printStack();
  75.  
  76.         while (reduce()) {
  77.             printStack();
  78.         }
  79.  
  80.         i++;
  81.     }
  82.  
  83.     while (reduce()) {
  84.         printStack();
  85.     }
  86.  
  87.     if (top == 0 && stack[top] == 'E') {
  88.         printf("String Accepted\n");
  89.     } else {
  90.         printf("String Rejected\n");
  91.     }
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
a+    b*c
stdout
copy 
Enter an Expression: 
Parsing Steps:
Shift: a
a
Reduce: id -> E
E
Shift: +
E+
Shift: b
E+b
Reduce: id -> E
E+E
Reduce: E + E -> E
E
Shift: *
E*
Shift: c
E*c
Reduce: id -> E
E*E
Reduce: E * E -> E
E
String Accepted
https://ideone.com/I90Ez3
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!