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.     // 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.     // 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.     // 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.     // E → id (lowercase letter)
  55.     if (top != -1 && islower(stack[top][0]) && strlen(stack[top]) == 1) {
  56.         pop();
  57.         push("E");
  58.         return 1;
  59.     }
  60.  
  61.     return 0;
  62. }
  63.  
  64. int main() {
  65.     printf("Enter expression: ");
  66.     fgets(input, sizeof(input), stdin);
  67.  
  68.     while (input[index]) {
  69.         if (isspace(input[index])) {
  70.             index++;
  71.             continue;
  72.         }
  73.  
  74.         // SHIFT
  75.         char temp[2] = {input[index], '\0'};
  76.         push(temp);
  77.         index++;
  78.  
  79.         printf("Shift: ");
  80.         printStack();
  81.  
  82.         // REDUCE
  83.         while (reduce()) {
  84.             printf("Reduce: ");
  85.             printStack();
  86.         }
  87.     }
  88.  
  89.     if (top == 0 && strcmp(stack[0], "E") == 0)
  90.         printf("String Accepted\n");
  91.     else
  92.         printf("String Rejected\n");
  93.  
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter expression: String Rejected
https://ideone.com/yOgs5r
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!