fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5. // Array functioning as our parsing stack
  6. char p_stack[100][10];
  7. int sp = -1;        // Stack pointer
  8. int cursor = 0;     // Tracks current position in the input string
  9. char expr_str[100]; // Stores the user's expression
  10.  
  11. // Add a token to the top of the stack
  12. void push_sym(const char *val) {
  13.     strcpy(p_stack[++sp], val);
  14. }
  15.  
  16. // Remove the topmost token
  17. void pop_sym() {
  18.     if (sp >= 0) {
  19.         sp--;
  20.     }
  21. }
  22.  
  23. // Output the current state of the stack
  24. void show_stack() {
  25.     for (int k = 0; k <= sp; k++) {
  26.         printf("%s ", p_stack[k]);
  27.     }
  28.     printf("\n");
  29. }
  30.  
  31. // Check if the top of the stack matches any grammar rules
  32. int attempt_reduction() {
  33.     // Rule: E -> ( E )
  34.     if (sp >= 2 &&
  35.         strcmp(p_stack[sp - 2], "(") == 0 &&
  36.         strcmp(p_stack[sp - 1], "E") == 0 &&
  37.         strcmp(p_stack[sp], ")") == 0) {
  38.         pop_sym(); pop_sym(); pop_sym();
  39.         push_sym("E");
  40.         return 1;
  41.     }
  42.  
  43.     // Rule: E -> E + E
  44.     if (sp >= 2 &&
  45.         strcmp(p_stack[sp - 2], "E") == 0 &&
  46.         strcmp(p_stack[sp - 1], "+") == 0 &&
  47.         strcmp(p_stack[sp], "E") == 0) {
  48.         pop_sym(); pop_sym(); pop_sym();
  49.         push_sym("E");
  50.         return 1;
  51.     }
  52.  
  53.     // Rule: E -> E * E
  54.     if (sp >= 2 &&
  55.         strcmp(p_stack[sp - 2], "E") == 0 &&
  56.         strcmp(p_stack[sp - 1], "*") == 0 &&
  57.         strcmp(p_stack[sp], "E") == 0) {
  58.         pop_sym(); pop_sym(); pop_sym();
  59.         push_sym("E");
  60.         return 1;
  61.     }
  62.  
  63.     // Rule: E -> id (any single lowercase char)
  64.     if (sp != -1 && islower(p_stack[sp][0]) && strlen(p_stack[sp]) == 1) {
  65.         pop_sym();
  66.         push_sym("E");
  67.         return 1;
  68.     }
  69.  
  70.     return 0; // No rule matched
  71. }
  72.  
  73. int main() {
  74.     printf("Input an arithmetic expression: ");
  75.     // Read the string including spaces
  76.     fgets(expr_str, sizeof(expr_str), stdin);
  77.  
  78.     // Strip the trailing newline character if it exists
  79.     expr_str[strcspn(expr_str, "\n")] = 0;
  80.  
  81.     while (expr_str[cursor] != '\0') {
  82.         // 1. Skip over any whitespaces
  83.         if (isspace(expr_str[cursor])) {
  84.             cursor++;
  85.             continue;
  86.         }
  87.  
  88.         // 2. Perform SHIFT operation
  89.         char sym_buf[2] = {expr_str[cursor], '\0'};
  90.         push_sym(sym_buf);
  91.         cursor++;
  92.  
  93.         printf("Action [Shift]:  ");
  94.         show_stack();
  95.  
  96.         // 3. Perform REDUCE operation as long as rules match
  97.         while (attempt_reduction()) {
  98.             printf("Action [Reduce]: ");
  99.             show_stack();
  100.         }
  101.     }
  102.  
  103.     // Final validation: Stack should contain only 'E'
  104.     if (sp == 0 && strcmp(p_stack[0], "E") == 0) {
  105.         printf("Result: String Accepted\n");
  106.     } else {
  107.         printf("Result: String Rejected\n");
  108.     }
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.02s 12136KB
comments (?)
stdin
copy 
(a + ( b * c))
stdout
copy 
Input an arithmetic expression: Action [Shift]:  ( 
Action [Shift]:  ( a 
Action [Reduce]: ( E 
Action [Shift]:  ( E + 
Action [Shift]:  ( E + ( 
Action [Shift]:  ( E + ( b 
Action [Reduce]: ( E + ( E 
Action [Shift]:  ( E + ( E * 
Action [Shift]:  ( E + ( E * c 
Action [Reduce]: ( E + ( E * E 
Action [Reduce]: ( E + ( E 
Action [Shift]:  ( E + ( E ) 
Action [Reduce]: ( E + E 
Action [Reduce]: ( E 
Action [Shift]:  ( E ) 
Action [Reduce]: E 
Result: String Accepted
https://ideone.com/hft5Ed
language:
Objective-C (clang 8.0)
created:
6 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!