fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5. char stack[100][20];
  6. int top = -1;
  7.  
  8. void push(const char *s) { strcpy(stack[++top], s); }
  9. void pop(int n) { top -= n; }
  10.  
  11. void printStack() {
  12.     printf("  Stack: [ ");
  13.     for (int i = 0; i <= top; i++) printf("%s ", stack[i]);
  14.     printf("]\n");
  15. }
  16.  
  17. int reduce() {
  18.     int reduced = 0, again = 1;
  19.     while (again) {
  20.         again = 0;
  21.         // Rule: E -> id
  22.         if (top >= 0 && isalpha(stack[top][0]) && strcmp(stack[top], "E") != 0) {
  23.             printf("  Reduce  id  → E   (token: %s)\n", stack[top]);
  24.             pop(1); push("E");
  25.             again = reduced = 1;
  26.         }
  27.         // Rule: E -> ( E )
  28.         else if (top >= 2 && !strcmp(stack[top-2], "(") && !strcmp(stack[top-1], "E") && !strcmp(stack[top], ")")) {
  29.             printf("  Reduce  ( E ) → E\n");
  30.             pop(3); push("E");
  31.             again = reduced = 1;
  32.         }
  33.         // Rule: E -> E * E
  34.         else if (top >= 2 && !strcmp(stack[top-2], "E") && !strcmp(stack[top-1], "*") && !strcmp(stack[top], "E")) {
  35.             printf("  Reduce  E * E → E\n");
  36.             pop(3); push("E");
  37.             again = reduced = 1;
  38.         }
  39.         // Rule: E -> E + E
  40.         else if (top >= 2 && !strcmp(stack[top-2], "E") && !strcmp(stack[top-1], "+") && !strcmp(stack[top], "E")) {
  41.             printf("  Reduce  E + E → E\n");
  42.             pop(3); push("E");
  43.             again = reduced = 1;
  44.         }
  45.     }
  46.     return reduced;
  47. }
  48.  
  49. int main() {
  50.     char input[200], tok[20];
  51.     printf("Enter expression: ");
  52.     if (!fgets(input, sizeof(input), stdin)) return 1;
  53.  
  54.     for (int i = 0; input[i]; ) {
  55.         while (isspace(input[i])) i++;
  56.         if (!input[i]) break;
  57.  
  58.         int j = 0;
  59.         if (isalpha(input[i]) || input[i] == '_') {
  60.             while (isalnum(input[i]) || input[i] == '_') tok[j++] = input[i++];
  61.         } else {
  62.             tok[j++] = input[i++];
  63.         }
  64.         tok[j] = '\0';
  65.  
  66.         if (!isalpha(tok[0]) && !strchr("_()+*", tok[0])) {
  67.             printf("  Unknown token '%s' — rejected.\nString Rejected\n", tok);
  68.             return 0;
  69.         }
  70.  
  71.         printf("Shift  '%s'\n", tok);
  72.         push(tok);
  73.         printStack();
  74.         reduce();
  75.         printStack();
  76.     }
  77.  
  78.     while (reduce()) printStack();
  79.  
  80.     if (top == 0 && !strcmp(stack[0], "E"))
  81.         printf("\nString Accepted ✓\n");
  82.     else {
  83.         printf("\nString Rejected ✗  (stack has %d item(s))\n", top + 1);
  84.         printStack();
  85.     }
  86.     return 0;
  87. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
(a+b *c)
stdout
copy 
Enter expression: Shift  '('
  Stack: [ ( ]
  Stack: [ ( ]
Shift  'a'
  Stack: [ ( a ]
  Reduce  id  → E   (token: a)
  Stack: [ ( E ]
Shift  '+'
  Stack: [ ( E + ]
  Stack: [ ( E + ]
Shift  'b'
  Stack: [ ( E + b ]
  Reduce  id  → E   (token: b)
  Reduce  E + E → E
  Stack: [ ( E ]
Shift  '*'
  Stack: [ ( E * ]
  Stack: [ ( E * ]
Shift  'c'
  Stack: [ ( E * c ]
  Reduce  id  → E   (token: c)
  Reduce  E * E → E
  Stack: [ ( E ]
Shift  ')'
  Stack: [ ( E ) ]
  Reduce  ( E ) → E
  Stack: [ E ]

String Accepted ✓
https://ideone.com/BwSJa9
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!