c evaluador de expresión
https://stackoverflow.com/questions/1465909
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Bien, digamos que tengo una cadena como esta en un archivo de texto:
((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
después de analizar esto en el programa c y las variables se manejan y configuran correctamente, terminará luciendo algo como esto:
((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
¿Existen bibliotecas útiles para evaluar expresiones que se representan como una cadena como esta?Estaba pensando que podría simplemente llamar a un programa Perl con la cadena como argumento que podría devolver el resultado fácilmente, pero no estaba seguro de si había una biblioteca en C que hiciera esto o si existía algún algoritmo conocido para resolverlo. tales expresiones?
EDITAR: Lo que realmente estoy buscando es algo que proporcione una respuesta a esta expresión, tal vez analizar sea una mala palabra.es decir.1 o 0
En pocas palabras, es un archivo que contiene un montón de expresiones aleatorias (que ya se sabe que están en el formato correcto) que deben evaluarse como 0 o 1.(arriba se evalúa como 1 porque da como resultado (1 Y 1).
Solución
He intentado escribir el código más compacto C para este problema bool evaluación de la expresión. Aquí está mi código final:
EDITAR: suprimido
Aquí es el manejo negación añadido:
EDIT: código de prueba añadió
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; }
}
}
Pruebas:
#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 );
}
Otros consejos
Puede incrustar lua en su programa y luego llamar a su intérprete para evaluar la expresión.
Es bastante fácil de rodar su propia recursiva descenso analizador de expresiones simples como estos.
I tiene un programa similar en torno a ese implemento analizador recursivo decente así que me cepillo hacia arriba y aquí 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;
}
Y este es un código de prueba:
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;
}
Esto es divertido: -D.
Lex y Yacc todavía son la mejor herramientas para tareas de análisis sencillos como éste.
Hace un tiempo, escribí un evaluador de expresiones C completo (es decir,expresiones evaluadas escritas usando sintaxis C) para un procesador de línea de comando y lenguaje de secuencias de comandos en un sistema integrado.solía este descripción del algoritmo como punto de partida.Podrías usar el código adjunto directamente, pero no me gustó la implementación y escribí el mío propio a partir de la descripción del algoritmo.Necesita algo de trabajo para admitir todos los operadores, llamadas a funciones y variables de C, pero es una explicación clara y, por lo tanto, un buen punto de partida, especialmente si no necesita ese nivel de integridad.
El principio básico es que la evaluación de expresiones es más fácil para una computadora que usa una pila y 'Notación polaca inversa', por lo que el algoritmo convierte una expresión de notación fija con orden de precedencia asociado y paréntesis a RPN, y luego la evalúa sacando operandos. realizar operaciones y enviar resultados, hasta que no queden operaciones y quede un valor en la pila.
Escribir un analizador de expresiones es fácil en principio, pero necesita una buena cantidad de esfuerzo.
Aquí hay un descenso básica recursivo-analizador para abajo la expresión he escrito en Java: http://david.tribble.com/src/java/ Tribble / análisis sintáctico / sql / QueryParser.java http://david.tribble.com/src/java/ Tribble / análisis sintáctico / sql / ExprLexer.java http://david.tribble.com/src/java/ Tribble / análisis sintáctico / sql / ExprLexer.java http://david.tribble.com/docs/tribble/ analizar / sql / package-summary.html
Esto puede no ser exactamente lo que está buscando, pero le dará una idea de lo que necesita.
