parse_predicates.c

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

// x ( ) < > == <= >= != && ||

typedef enum {var, open, close, less, greater, equals, not_greater, not_less, not_equal, and, or, number} operator_t;

operator_t parse_operator(char *op) {
    switch(*op)
    {
        case 'x': return var;
        case '(': return open;
        case ')': return close;
        case '<':
            if(*(op + 1) == '=')
                return not_greater;
            else
                return less;
        case '>':
            if(*(op + 1) == '=')
                return not_less;
            else
                return greater;
        case '=': return equals;
        case '!':
            return not_equal;
        case '&': return and;
        case '|': return or;
        default: return number;
    }
}

size_t operator_length(operator_t op) {
    if(op == number)
        return 0;
    if(op == var ||
        op == open ||
        op == close ||
        op == less ||
        op == greater)
            return 1;
    return 2;
}

bool is_digit(char c) {
    return c - '0' >= 0 && c - '0' <= 9;
}

bool is_comparison_operator(operator_t op) {
    return op == less ||
            op == greater ||
            op == equals ||
            op == not_greater ||
            op == not_less ||
            op == not_equal;
}

bool is_primary_operand(operator_t op) {
    return op == number || op == var;
}

bool evaluate(operator_t *op_tokens, int *num_tokens, size_t num, int x, bool *error) {
    *error = false;
    if(num == 3) {
        if(!is_comparison_operator(op_tokens[1]) ||
            !is_primary_operand(op_tokens[0]) ||
            !is_primary_operand(op_tokens[2])) {
            *error = true;
            return false;
        }
        switch(op_tokens[1]) {
            case less: return num_tokens[0] < num_tokens[2];
            case greater: return num_tokens[0] > num_tokens[2];
            case equals: return num_tokens[0] == num_tokens[2];
            case not_greater: return num_tokens[0] <= num_tokens[2];
            case not_less: return num_tokens[0] >= num_tokens[2];
            case not_equal: return num_tokens[0] != num_tokens[2];
            default:
                *error = true;
                return false;
        }
    }
    int scope = 0;
    for(int i = num - 1; i >= 0; i--) {
        if(op_tokens[i] == close)
            scope++;
        if(op_tokens[i] == open)
            scope--;
        if(scope == 0 && op_tokens[i] == or) {
            return evaluate(op_tokens, num_tokens, i, x, error) ||
                    evaluate(op_tokens + i + 1, num_tokens + i + 1, num - i - 1, x, error);
        }
    }
    scope = 0;
    for(int i = num - 1; i >= 0; i--) {
        if(op_tokens[i] == close)
            scope++;
        if(op_tokens[i] == open)
            scope--;
        if(scope == 0 && op_tokens[i] == and) {
            return evaluate(op_tokens, num_tokens, i, x, error) &&
                    evaluate(op_tokens + i + 1, num_tokens + i + 1, num - i - 1, x, error);
        }
    }
    if(op_tokens[0] == open && op_tokens[num - 1] == close) {
        return evaluate(op_tokens + 1, num_tokens + 1, num - 2, x, error);
    }
    *error = true;
    return false;
}

bool parse_predicate(char *pred, int x, bool *error) {
    *error = false;
    int *num_tokens = NULL;
    operator_t *op_tokens = NULL;
    int current_token = -1;
    size_t scope = 0;
    bool parsing_number = false;
    bool parsing_negative = false;
    for(size_t i = 0; i < strlen(pred); i++) {
        if(parsing_number) {
            if(is_digit(pred[i])) {
                num_tokens[current_token] *= 10;
                num_tokens[current_token] += pred[i] - '0';
                continue;
            }
            else {
                parsing_number = false;
                if(parsing_negative)
                    num_tokens[current_token] *= -1;
            }
        }
        if(pred[i] == ' ' || pred[i] == '\0' || pred[i] == '\n')
            continue;
        num_tokens = realloc(num_tokens, (++current_token + 1) * sizeof(int));
        op_tokens = realloc(op_tokens, (current_token + 1) * sizeof(operator_t));
        operator_t current_operator = parse_operator(pred + i);
        size_t current_operator_length = operator_length(current_operator);
        if(current_operator == number && is_digit(pred[i])) {
            op_tokens[current_token] = number;
            parsing_number = true;
            parsing_negative = false;
            num_tokens[current_token] = pred[i] - '0';
            continue;
        }
        if(pred[i] == '-') {
            op_tokens[current_token] = number;
            parsing_number = true;
            parsing_negative = true;
            num_tokens[current_token] = 0;
            continue;
        }
        if(current_operator == var) {
            op_tokens[current_token] = number;
            num_tokens[current_token] = x;
            continue;
        }
        if(current_operator != number) {
            op_tokens[current_token] = current_operator;
            num_tokens[current_token] = 0;
            i += current_operator_length - 1;
            if(current_operator == open)
                scope++;
            if(current_operator == close)
                scope--;
        }
        if(current_operator == number && !is_digit(pred[i])) {
            *error = true;
            return false;
        }
    }
    if(scope != 0) {
        *error = true;
        return false;
    }
    size_t tokens_num = current_token + 1;
    return evaluate(op_tokens, num_tokens, tokens_num, x, error);
}


        /*if(op_tokens[i] == number) {
            printf("[number]   %d", num_tokens[i]);
        }
        else {
            printf("[operator] ");
            switch (op_tokens[i])
            {
                case var: printf("x"); break;
                case open: printf("("); break;
                case close: printf(")"); break;
                case less: printf("<"); break;
                case greater: printf(">"); break;
                case equals: printf("=="); break;
                case not_greater: printf("<="); break;
                case not_less: printf(">="); break;
                case not_equal: printf("!="); break;
                case not: printf("!"); break;
                case and: printf("&&"); break;
                case or: printf("||"); break;
            }
        }
        printf("\n");
        */

int main() {
    size_t bufsize = 256;
    char *predicate = (char *)malloc(bufsize * sizeof(char));
    int x;
    printf("predicate: ");
    getline(&predicate, &bufsize, stdin);
    printf("x value: ");
    scanf("%d", &x);
    bool error;
    bool result = parse_predicate(predicate, x, &error);
    printf("result: %d, error:  %d\n", result, error);
    free(predicate);
}