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