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 idx = 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. // Print stack with spaces between symbols (matches expected output)
  19. void printStack() {
  20.     for (int i = 0; i <= top; i++) printf("%s ", stack[i]);
  21.     printf("\n");
  22. }
  23.  
  24. int reduce() {
  25.     // Rule 1: E → E + E
  26.     if (top >= 2 &&
  27.         strcmp(stack[top-2], "E") == 0 &&
  28.         strcmp(stack[top-1], "+") == 0 &&
  29.         strcmp(stack[top],   "E") == 0) {
  30.         pop(); pop(); pop();
  31.         push("E");
  32.         return 1;
  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.     // Rule 3: E → (E)
  44.     if (top >= 2 &&
  45.         strcmp(stack[top-2], "(") == 0 &&
  46.         strcmp(stack[top-1], "E") == 0 &&
  47.         strcmp(stack[top],   ")") == 0) {
  48.         pop(); pop(); pop();
  49.         push("E");
  50.         return 1;
  51.     }
  52.     // Rule 4: E → id
  53.     if (top != -1 && stack[top][0] >= 'a' && stack[top][0] <= 'z') {
  54.         pop();
  55.         push("E");
  56.         return 1;
  57.     }
  58.     return 0;
  59. }
  60.  
  61. int main() {
  62.     printf("Enter an Expression:\n");
  63.     fgets(input, sizeof(input), stdin); // fgets allows spaces in input
  64.  
  65.     while (input[idx]) {
  66.         // Skip whitespace characters
  67.         if (isspace(input[idx])) {
  68.             idx++;
  69.             continue;
  70.         }
  71.  
  72.         char temp[2] = {input[idx], '\0'};
  73.         push(temp);
  74.         idx++;
  75.  
  76.         printf("Shift: ");
  77.         printStack();
  78.  
  79.         while (reduce()) {
  80.             printf("Reduce: ");
  81.             printStack();
  82.         }
  83.     }
  84.  
  85.     if (top == 0 && strcmp(stack[0], "E") == 0)
  86.         printf("String Accepted\n");
  87.     else
  88.         printf("String Rejected\n");
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
(a + (b*a))
stdout
copy 
Enter an Expression:
Shift: ( 
Shift: ( a 
Reduce: ( E 
Shift: ( E + 
Shift: ( E + ( 
Shift: ( E + ( b 
Reduce: ( E + ( E 
Shift: ( E + ( E * 
Shift: ( E + ( E * a 
Reduce: ( E + ( E * E 
Reduce: ( E + ( E 
Shift: ( E + ( E ) 
Reduce: ( E + E 
Reduce: ( E 
Shift: ( E ) 
Reduce: E 
String Accepted
https://ideone.com/v2cXLZ
language:
C (gcc 8.3)
created:
14 hours 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!