вычислитель выражений c

Question

Хорошо, допустим, у меня есть такая строка в текстовом файле:

((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))

после того, как это будет проанализировано в программе c и переменные будут обработаны и установлены правильно, в конечном итоге это будет выглядеть примерно так:

((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))

Существуют ли какие-либо полезные библиотеки для вычисления выражений, которые представлены в виде одной строки, подобной этой?Я думал, что мог бы просто вызвать программу на perl со строкой в качестве аргумента, которая могла бы легко возвращать результат, но не был уверен, есть ли в C библиотека, которая это делает, или существуют ли какие-либо известные алгоритмы для решения таких выражений?

РЕДАКТИРОВАТЬ: На самом деле я ищу что-то, что выдавало бы ответ на это выражение, возможно, parse было плохим словом.т. е.1 или 0

В ореховой скорлупе это файл, содержащий кучу случайных выражений (уже известно, что они в правильном формате), которые должны быть оценены либо в 0, либо в 1.(приведенное выше значение равно 1, потому что это приводит к (1 И 1).

Answer 1

Я попытался написать наиболее компактный код на языке Си для этой задачи вычисления выражения bool.Вот мой окончательный код:

Редактировать:удалено

Вот добавленная обработка отрицания:

Редактировать:добавлен тестовый код

char *eval( char *expr, int *res ){
  enum { LEFT, OP1, MID, OP2, RIGHT } state = LEFT;
  enum { AND, OR } op;
  int mid=0, tmp=0, NEG=0;

  for( ; ; expr++, state++, NEG=0 ){
    for( ;; expr++ )
         if( *expr == '!'     ) NEG = !NEG;
    else if( *expr != ' '     ) break;

         if( *expr == '0'     ){ tmp  =  NEG; }
    else if( *expr == '1'     ){ tmp  = !NEG; }
    else if( *expr == 'A'     ){ op   = AND; expr+=2; }
    else if( *expr == '&'     ){ op   = AND; expr+=1; }
    else if( *expr == 'O'     ){ op   = OR;  expr+=1; }
    else if( *expr == '|'     ){ op   = OR;  expr+=1; }
    else if( *expr == '('     ){ expr = eval( expr+1, &tmp ); if(NEG) tmp=!tmp; }
    else if( *expr == '\0' ||
             *expr == ')'     ){ if(state == OP2) *res |= mid; return expr; }

         if( state == LEFT               ){ *res  = tmp;               }
    else if( state == MID   && op == OR  ){  mid  = tmp;               }
    else if( state == MID   && op == AND ){ *res &= tmp; state = LEFT; }
    else if( state == OP2   && op == OR  ){ *res |= mid; state = OP1;  }
    else if( state == RIGHT              ){  mid &= tmp; state = MID;  }
  }
}

Тестирование:

#include <stdio.h> 

void test( char *expr, int exprval ){
  int result;
  eval( expr, &result );
  printf("expr: '%s' result: %i  %s\n",expr,result,result==exprval?"OK":"FAILED");
}
#define TEST(x)   test( #x, x ) 

#define AND       && 
#define OR        || 

int main(void){
  TEST( ((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1)) );
  TEST( !(0 OR (1 AND 0)) OR !1 AND 0 );
}

Answer 2

Вы можете встроить lua в вашей программе, а затем вызовите ее интерпретатор для вычисления выражения.

Answer 3

Это достаточно легко сделать самостоятельно анализатор рекурсивного спуска для простых выражений, подобных этим.

Answer 4

У меня есть похожая программа, которая реализует рекурсивно-приличный синтаксический анализатор, поэтому я обновляю ее, и вот она.

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


int doOR(int pOprd1, int pOprd2) {
    если (pOprd1 == -1) вернуть pOprd2;вернуть pOprd1 || pOprd2;} 
int doAND(int pOprd1, int pOprd2) {
    if (pOprd1 == -1) возвращает pOprd2;вернуть pOprd1 && pOprd2;} 
int doProcess(char pOpert, int pOprd1, int pOprd2) {
    if (pOpert == '0') возвращает pOprd2;if (pOpert == 'O') обратная дверь (pOprd1, pOprd2);if (pOpert == 'A') возвращает doAND(pOprd1, pOprd2);ставит ("Неизвестный оператор!!!");выход (-1);} 
int* doParse(символ  pStr, int pStart) {
    символ C;int i = pStart ( начальный );значение int = -1;оператор символа = '0';для(;(C = pStr[i]) != 0;i++) {
        if (C == '0') { Значение = doProcess(оператор, значение, 0);продолжать;}
        if (C == '1') { Значение = doProcess(Оператор, значение, 1);продолжать;}
        если (C == ' ') продолжить;if (C == ')') {
            int  аРетурн;aReturn = malloc(2*размер aReturn);aReturn[0] = Значение;aReturn[1] = i + 1;возврат aReturn;}
        if (C == '(') {
            int * Результат = doParse(pStr, i + 1);Значение = doProcess(Оператор, Значение, результат [0]);i = Результат[1];if (pStr[i] == 0) разрыв;продолжать;}
        if ((C == 'A') && ((pStr[i + 1] == 'N') && (pStr[i + 2] == 'D'))) {
            if ((Оператор == '0') || (Оператор == 'A')) {
                Оператор = 'A';i += 2;продолжать;} else {
                ставит("Операторы смешивания не разрешены (И)!!!");выход (-1);}
        }
        if ((C == 'O') && (pStr[i + 1] == 'R')) {
            if ((Оператор == '0') || (Оператор == 'O')) {
                Оператор = 'O';i += 1;продолжать;} else {
                ставит("Операторы микширования не разрешены (ИЛИ)!!!");выход (-1);}
        }
        printf("Неизвестный символ:'%c (\"%s\"[%d])'!!!", C, pStr, i);выход (-1);}
    инт* аРетурн;aReturn = malloc(2*размер aReturn);aReturn[0] = Значение;aReturn[1] = i;возврат aReturn;}

И это тестовый код:

int main(void) {
    char* aExpr   = "1";
    int*  aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "0";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "1 AND 0";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "1 AND 1";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "0 OR 0 OR 0";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "1 OR 0 OR 0";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "1 OR 1 OR 0";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "(1 OR 0)";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "(0 OR 0)";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    aExpr   = "((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))";
    aResult = doParse(aExpr, 0);
    printf("%s = %d\n", aExpr, ((int*)aResult)[0]);
    free(aResult);
    puts("DONE!!!");
    return EXIT_SUCCESS;
}

Это весело :-D.

Answer 5

Я верю Лекс и Якк по-прежнему являются лучшими инструментами для простых задач синтаксического анализа, подобных этой.

Answer 6

Некоторое время назад я написал полный вычислитель выражений C (т.е.вычисляемые выражения, написанные с использованием синтаксиса C) для процессора командной строки и языка сценариев во встроенной системе.Я использовал это описание алгоритма в качестве отправной точки.Вы могли бы использовать сопроводительный код напрямую, но мне не понравилась реализация, и я написал свой собственный на основе описания алгоритма.Потребовалась некоторая работа для поддержки всех операторов C, вызовов функций и переменных, но это четкое объяснение и, следовательно, хорошая отправная точка, особенно если вам не нужен такой уровень полноты.

Основной принцип заключается в том, что вычисление выражения проще для компьютера, использующего стек и "Обратную польскую нотацию", поэтому алгоритм преобразует исправленное выражение нотации с соответствующим порядком приоритета и круглыми скобками в RPN, а затем вычисляет его, вставляя операнды, выполняя операции и отправляя результаты, пока не останется операций и одного значения в стеке.

Answer 7

Написать анализатор выражений в принципе несложно, но требует изрядных усилий.

Вот базовый анализатор выражений с рекурсивным спуском, который я написал на Java: http://david.tribble.com/src/java/tribble/parse/sql/QueryParser.java http://david.tribble.com/src/java/tribble/parse/sql/ExprLexer.java http://david.tribble.com/src/java/tribble/parse/sql/ExprLexer.java http://david.tribble.com/docs/tribble/parse/sql/package-summary.html

Возможно, это не совсем то, что вы ищете, но это даст вам представление о том, что вам нужно.