вычислитель выражений c
-
13-09-2019 - |
Вопрос
Хорошо, допустим, у меня есть такая строка в текстовом файле:
((( 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).
Решение
Я попытался написать наиболее компактный код на языке Си для этой задачи вычисления выражения 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 );
}
Другие советы
Вы можете встроить lua в вашей программе, а затем вызовите ее интерпретатор для вычисления выражения.
Это достаточно легко сделать самостоятельно анализатор рекурсивного спуска для простых выражений, подобных этим.
У меня есть похожая программа, которая реализует рекурсивно-приличный синтаксический анализатор, поэтому я обновляю ее, и вот она.
#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.
Я верю Лекс и Якк по-прежнему являются лучшими инструментами для простых задач синтаксического анализа, подобных этой.
Некоторое время назад я написал полный вычислитель выражений C (т.е.вычисляемые выражения, написанные с использованием синтаксиса C) для процессора командной строки и языка сценариев во встроенной системе.Я использовал это описание алгоритма в качестве отправной точки.Вы могли бы использовать сопроводительный код напрямую, но мне не понравилась реализация, и я написал свой собственный на основе описания алгоритма.Потребовалась некоторая работа для поддержки всех операторов C, вызовов функций и переменных, но это четкое объяснение и, следовательно, хорошая отправная точка, особенно если вам не нужен такой уровень полноты.
Основной принцип заключается в том, что вычисление выражения проще для компьютера, использующего стек и "Обратную польскую нотацию", поэтому алгоритм преобразует исправленное выражение нотации с соответствующим порядком приоритета и круглыми скобками в RPN, а затем вычисляет его, вставляя операнды, выполняя операции и отправляя результаты, пока не останется операций и одного значения в стеке.
Написать анализатор выражений в принципе несложно, но требует изрядных усилий.
Вот базовый анализатор выражений с рекурсивным спуском, который я написал на 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
Возможно, это не совсем то, что вы ищете, но это даст вам представление о том, что вам нужно.