dreadmachine

parse_predicates.c

Oct 22nd, 2021
552
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. #include <string.h>
  4. #include <stdlib.h>
  5.  
  6. // x ( ) < > == <= >= != && ||
  7.  
  8. typedef enum {var, open, close, less, greater, equals, not_greater, not_less, not_equal, and, or, number} operator_t;
  9.  
  10. operator_t parse_operator(char *op) {
  11.     switch(*op)
  12.     {
  13.         case 'x': return var;
  14.         case '(': return open;
  15.         case ')': return close;
  16.         case '<':
  17.             if(*(op + 1) == '=')
  18.                 return not_greater;
  19.             else
  20.                 return less;
  21.         case '>':
  22.             if(*(op + 1) == '=')
  23.                 return not_less;
  24.             else
  25.                 return greater;
  26.         case '=': return equals;
  27.         case '!':
  28.             return not_equal;
  29.         case '&': return and;
  30.         case '|': return or;
  31.         default: return number;
  32.     }
  33. }
  34.  
  35. size_t operator_length(operator_t op) {
  36.     if(op == number)
  37.         return 0;
  38.     if(op == var ||
  39.         op == open ||
  40.         op == close ||
  41.         op == less ||
  42.         op == greater)
  43.             return 1;
  44.     return 2;
  45. }
  46.  
  47. bool is_digit(char c) {
  48.     return c - '0' >= 0 && c - '0' <= 9;
  49. }
  50.  
  51. bool is_comparison_operator(operator_t op) {
  52.     return op == less ||
  53.             op == greater ||
  54.             op == equals ||
  55.             op == not_greater ||
  56.             op == not_less ||
  57.             op == not_equal;
  58. }
  59.  
  60. bool is_primary_operand(operator_t op) {
  61.     return op == number || op == var;
  62. }
  63.  
  64. bool evaluate(operator_t *op_tokens, int *num_tokens, size_t num, int x, bool *error) {
  65.     *error = false;
  66.     if(num == 3) {
  67.         if(!is_comparison_operator(op_tokens[1]) ||
  68.             !is_primary_operand(op_tokens[0]) ||
  69.             !is_primary_operand(op_tokens[2])) {
  70.             *error = true;
  71.             return false;
  72.         }
  73.         switch(op_tokens[1]) {
  74.             case less: return num_tokens[0] < num_tokens[2];
  75.             case greater: return num_tokens[0] > num_tokens[2];
  76.             case equals: return num_tokens[0] == num_tokens[2];
  77.             case not_greater: return num_tokens[0] <= num_tokens[2];
  78.             case not_less: return num_tokens[0] >= num_tokens[2];
  79.             case not_equal: return num_tokens[0] != num_tokens[2];
  80.             default:
  81.                 *error = true;
  82.                 return false;
  83.         }
  84.     }
  85.     int scope = 0;
  86.     for(int i = num - 1; i >= 0; i--) {
  87.         if(op_tokens[i] == close)
  88.             scope++;
  89.         if(op_tokens[i] == open)
  90.             scope--;
  91.         if(scope == 0 && op_tokens[i] == or) {
  92.             return evaluate(op_tokens, num_tokens, i, x, error) ||
  93.                     evaluate(op_tokens + i + 1, num_tokens + i + 1, num - i - 1, x, error);
  94.         }
  95.     }
  96.     scope = 0;
  97.     for(int i = num - 1; i >= 0; i--) {
  98.         if(op_tokens[i] == close)
  99.             scope++;
  100.         if(op_tokens[i] == open)
  101.             scope--;
  102.         if(scope == 0 && op_tokens[i] == and) {
  103.             return evaluate(op_tokens, num_tokens, i, x, error) &&
  104.                     evaluate(op_tokens + i + 1, num_tokens + i + 1, num - i - 1, x, error);
  105.         }
  106.     }
  107.     if(op_tokens[0] == open && op_tokens[num - 1] == close) {
  108.         return evaluate(op_tokens + 1, num_tokens + 1, num - 2, x, error);
  109.     }
  110.     *error = true;
  111.     return false;
  112. }
  113.  
  114. bool parse_predicate(char *pred, int x, bool *error) {
  115.     *error = false;
  116.     int *num_tokens = NULL;
  117.     operator_t *op_tokens = NULL;
  118.     int current_token = -1;
  119.     size_t scope = 0;
  120.     bool parsing_number = false;
  121.     bool parsing_negative = false;
  122.     for(size_t i = 0; i < strlen(pred); i++) {
  123.         if(parsing_number) {
  124.             if(is_digit(pred[i])) {
  125.                 num_tokens[current_token] *= 10;
  126.                 num_tokens[current_token] += pred[i] - '0';
  127.                 continue;
  128.             }
  129.             else {
  130.                 parsing_number = false;
  131.                 if(parsing_negative)
  132.                     num_tokens[current_token] *= -1;
  133.             }
  134.         }
  135.         if(pred[i] == ' ' || pred[i] == '\0' || pred[i] == '\n')
  136.             continue;
  137.         num_tokens = realloc(num_tokens, (++current_token + 1) * sizeof(int));
  138.         op_tokens = realloc(op_tokens, (current_token + 1) * sizeof(operator_t));
  139.         operator_t current_operator = parse_operator(pred + i);
  140.         size_t current_operator_length = operator_length(current_operator);
  141.         if(current_operator == number && is_digit(pred[i])) {
  142.             op_tokens[current_token] = number;
  143.             parsing_number = true;
  144.             parsing_negative = false;
  145.             num_tokens[current_token] = pred[i] - '0';
  146.             continue;
  147.         }
  148.         if(pred[i] == '-') {
  149.             op_tokens[current_token] = number;
  150.             parsing_number = true;
  151.             parsing_negative = true;
  152.             num_tokens[current_token] = 0;
  153.             continue;
  154.         }
  155.         if(current_operator == var) {
  156.             op_tokens[current_token] = number;
  157.             num_tokens[current_token] = x;
  158.             continue;
  159.         }
  160.         if(current_operator != number) {
  161.             op_tokens[current_token] = current_operator;
  162.             num_tokens[current_token] = 0;
  163.             i += current_operator_length - 1;
  164.             if(current_operator == open)
  165.                 scope++;
  166.             if(current_operator == close)
  167.                 scope--;
  168.         }
  169.         if(current_operator == number && !is_digit(pred[i])) {
  170.             *error = true;
  171.             return false;
  172.         }
  173.     }
  174.     if(scope != 0) {
  175.         *error = true;
  176.         return false;
  177.     }
  178.     size_t tokens_num = current_token + 1;
  179.     return evaluate(op_tokens, num_tokens, tokens_num, x, error);
  180. }
  181.  
  182.  
  183.         /*if(op_tokens[i] == number) {
  184.             printf("[number]   %d", num_tokens[i]);
  185.         }
  186.         else {
  187.             printf("[operator] ");
  188.             switch (op_tokens[i])
  189.             {
  190.                 case var: printf("x"); break;
  191.                 case open: printf("("); break;
  192.                 case close: printf(")"); break;
  193.                 case less: printf("<"); break;
  194.                 case greater: printf(">"); break;
  195.                 case equals: printf("=="); break;
  196.                 case not_greater: printf("<="); break;
  197.                 case not_less: printf(">="); break;
  198.                 case not_equal: printf("!="); break;
  199.                 case not: printf("!"); break;
  200.                 case and: printf("&&"); break;
  201.                 case or: printf("||"); break;
  202.             }
  203.         }
  204.         printf("\n");
  205.         */
  206.  
  207. int main() {
  208.     size_t bufsize = 256;
  209.     char *predicate = (char *)malloc(bufsize * sizeof(char));
  210.     int x;
  211.     printf("predicate: ");
  212.     getline(&predicate, &bufsize, stdin);
  213.     printf("x value: ");
  214.     scanf("%d", &x);
  215.     bool error;
  216.     bool result = parse_predicate(predicate, x, &error);
  217.     printf("result: %d, error:  %d\n", result, error);
  218.     free(predicate);
  219. }
RAW Paste Data