c expressão avaliador
https://stackoverflow.com/questions/1465909
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Ok, digamos que eu tenho uma string como esta em um arquivo de texto:
((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
após a análise desta para o programa c e os vars são manipulados e definir corretamente ele vai acabar procurando algo como isto:
((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
Existem quaisquer bibliotecas úteis lá fora, para avaliar expressões que são representados como uma cadeia como este? Eu estava pensando que eu poderia simplesmente chamar um programa perl com a string como um argumento de que seria capaz de retornar o resultado facilmente, mas não tinha certeza se havia uma biblioteca em C que fez isso, ou se existem algoritmos conhecidos para a resolução de tais expressões?
EDIT: O que eu estou procurando realmente é algo que iria cuspir uma resposta a esta expressão, talvez parse era uma palavra ruim. isto é, 1 ou 0
Em uma casca de noz é um ficheiro que contém um monte de expressões aleatórias (já conhecido por ser no formato certo) que precisam ser avaliados para 0 ou 1. (acima avalia a 1, pois resulta em (1 e 1 ).
Solução
Eu tentei escrever o código C mais compacto para este bool problema de avaliação de expressão. Aqui está o meu código final:
EDIT: apagado
Aqui é a manipulação negação acrescentou:
EDIT: código de teste adicionado
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; }
}
}
Testing:
#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 );
}
Outras dicas
Você pode incorporar lua em seu programa e, em seguida, chamá-lo de intérprete para avaliar a expressão.
É fácil o suficiente para rolar o seu próprio recursiva descida analisador para expressões simples como estas.
I tem programa semelhante em torno desse implementar parser recursivo decente então eu escová-lo para cima e aqui está.
#include <stdio.h>
#include <stdlib.h>
int doOR(int pOprd1, int pOprd2) {
if (pOprd1 == -1) return pOprd2;
return pOprd1 || pOprd2;
}
int doAND(int pOprd1, int pOprd2) {
if (pOprd1 == -1) return pOprd2;
return pOprd1 && pOprd2;
}
int doProcess(char pOpert, int pOprd1, int pOprd2) {
if (pOpert == '0') return pOprd2;
if (pOpert == 'O') return doOR (pOprd1, pOprd2);
if (pOpert == 'A') return doAND(pOprd1, pOprd2);
puts("Unknown Operator!!!");
exit(-1);
}
int* doParse(char pStr, int pStart) {
char C;
int i = pStart;
int Value = -1;
char Operator = '0';
for(; (C = pStr[i]) != 0; i++) {
if (C == '0') { Value = doProcess(Operator, Value, 0); continue; }
if (C == '1') { Value = doProcess(Operator, Value, 1); continue; }
if (C == ' ') continue;
if (C == ')') {
int aReturn;
aReturn = malloc(2*sizeof aReturn);
aReturn[0] = Value;
aReturn[1] = i + 1;
return aReturn;
}
if (C == '(') {
int * aResult = doParse(pStr, i + 1);
Value = doProcess(Operator, Value, aResult[0]);
i = aResult[1];
if (pStr[i] == 0) break;
continue;
}
if ((C == 'A') && ((pStr[i + 1] == 'N') && (pStr[i + 2] == 'D'))) {
if ((Operator == '0') || (Operator == 'A')) {
Operator = 'A';
i += 2;
continue;
} else {
puts("Mix Operators are not allowed (AND)!!!");
exit(-1);
}
}
if ((C == 'O') && (pStr[i + 1] == 'R')) {
if ((Operator == '0') || (Operator == 'O')) {
Operator = 'O';
i += 1;
continue;
} else {
puts("Mix Operators are not allowed (OR)!!!");
exit(-1);
}
}
printf("Unknown character: '%c (\"%s\"[%d])'!!!", C, pStr, i);
exit(-1);
}
int* aReturn;
aReturn = malloc(2*sizeof aReturn);
aReturn[0] = Value;
aReturn[1] = i;
return aReturn;
}
E este é um código de teste:
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;
}
Esta é divertido :-D.
Acredito Lex e Yacc ainda são a melhor ferramentas para tarefas de análise simples como este.
Um tempo atrás, eu escrevi um avaliador de expressão C completo (ou seja, expressões avaliadas escritos usando a sintaxe C) para um processador de linha de comando e linguagem de script em um sistema embarcado. Eu costumava esta descrição do algoritmo como um ponto de partida. Você poderia usar o código que acompanha diretamente, mas não o fiz como a implementação, e escrevi o meu próprio a partir da descrição algoritmo. É necessário algum trabalho para apoiar todos os operadores de C, chamadas de funções e variáveis, mas é uma explicação clara e, portanto, um bom ponto de partida, especialmente se você não precisa que o nível de completude.
O princípio básico é que a avaliação da expressão é mais fácil para um computador através de uma pilha e 'Reverse Polish Notation', então o algoritmo converte uma expressão da notação em-fix com a ordem associada de precedência e parênteses para RPN, e depois avalia-lo popping operandos, executando operações, e empurrando resultados, até que não haja operações à esquerda e um valor deixado na pilha.
Escrevendo um analisador de expressão é fácil, em princípio, mas leva uma quantidade razoável de esforço.
Aqui está um básico para-down analisador de expressão recursiva-descida eu escrevi em Java: http://david.tribble.com/src/java/ tribble / análise / sql / QueryParser.java http://david.tribble.com/src/java/ tribble / análise / sql / ExprLexer.java http://david.tribble.com/src/java/ tribble / análise / sql / ExprLexer.java http://david.tribble.com/docs/tribble/ parse / sql / package-summary.html
Isto pode não ser exatamente o que você está procurando, mas ele vai te dar uma idéia do que você precisa.
