fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. #define SIZE 100
  6.  
  7. char stack[SIZE];
  8. int top = -1;
  9.  
  10. char precedenceTable[7][7] = {
  11.     //      +    *    id   (    )    $ 
  12.     /* + */ {'>', '<', '<', '<', '>', '>'},
  13.     /* * */ {'>', '>', '<', '<', '>', '>'},
  14.     /*id */ {'>', '>', 'e', 'e', '>', '>'},
  15.     /* ( */ {'<', '<', '<', '<', 'e', 'e'},
  16.     /* ) */ {'>', '>', 'e', 'e', '>', '>'},
  17.     /* $ */ {'<', '<', '<', '<', '<', 'a'}
  18. };
  19.  
  20. char symbols[] = {'+', '*', 'i', '(', ')', '$'};
  21.  
  22. int getSymbolIndex(char sym) {
  23.     switch (sym) {
  24.         case '+': return 0;
  25.         case '*': return 1;
  26.         case 'i': return 2;  // identifier represented as 'i'
  27.         case '(': return 3;
  28.         case ')': return 4;
  29.         case '$': return 5;
  30.         default: return -1;
  31.     }
  32. }
  33.  
  34. char getTopTerminal() {
  35.     for (int i = top; i >= 0; i--) {
  36.         if (stack[i] != 'E') return stack[i];
  37.     }
  38.     return '$';
  39. }
  40.  
  41. void push(char c) {
  42.     stack[++top] = c;
  43. }
  44.  
  45. void pop() {
  46.     if (top >= 0) top--;
  47. }
  48.  
  49. void printStack() {
  50.     for (int i = 0; i <= top; i++)
  51.         printf("%c", stack[i]);
  52. }
  53.  
  54. int main() {
  55.     char input[SIZE];
  56.     printf("Enter expression (use 'i' for id): ");
  57.     scanf("%s", input);
  58.  
  59.     strcat(input, "$"); // append end symbol
  60.     push('$');
  61.  
  62.     int i = 0;
  63.     char a = input[i];
  64.  
  65.     printf("\nStack\t\tInput\t\tAction\n");
  66.  
  67.     while (1) {
  68.         char topTerminal = getTopTerminal();
  69.         char relation = precedenceTable[getSymbolIndex(topTerminal)][getSymbolIndex(a)];
  70.  
  71.         printStack();
  72.         printf("\t\t%s\t\t", &input[i]);
  73.  
  74.         if (a == '$' && top == 1 && stack[0] == '$' && stack[1] == 'E') {
  75.             printf("Accepted\n");
  76.             break;
  77.         }
  78.  
  79.         if (relation == '<' || relation == '=') {
  80.             printf("Shift\n");
  81.             push(a);
  82.             i++;
  83.             a = input[i];
  84.         } else if (relation == '>') {
  85.             printf("Reduce\n");
  86.             // Reduce: Replace pattern like E op E or (E) or i with E
  87.             if (stack[top] == 'i') {
  88.                 pop(); push('E');
  89.             } else if (stack[top] == 'E' && stack[top - 1] == '+' && stack[top - 2] == 'E') {
  90.                 top -= 2; stack[top] = 'E';
  91.             } else if (stack[top] == 'E' && stack[top - 1] == '*' && stack[top - 2] == 'E') {
  92.                 top -= 2; stack[top] = 'E';
  93.             } else if (stack[top] == ')' && stack[top - 1] == 'E' && stack[top - 2] == '(') {
  94.                 top -= 2; stack[top] = 'E';
  95.             } else {
  96.                 printf("Error in reduction\n");
  97.                 break;
  98.             }
  99.         } else {
  100.             printf("Error: Invalid expression\n");
  101.             break;
  102.         }
  103.     }
  104.  
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
i*i+i
stdout
copy 
Enter expression (use 'i' for id): 
Stack		Input		Action
$		i*i+i$		Shift
$i		*i+i$		Reduce
$E		*i+i$		Shift
$E*		i+i$		Shift
$E*i		+i$		Reduce
$E*E		+i$		Reduce
$E		+i$		Shift
$E+		i$		Shift
$E+i		$		Reduce
$E+E		$		Reduce
$E		$		Accepted
https://ideone.com/pHG25C
language:
C++14 (gcc 8.3)
created:
2 days 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!