c expression Evaluator
https://stackoverflow.com/questions/1465909
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Ok LETs dire que j'ai une chaîne telle que cela dans un fichier texte:
((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
après avoir analysé ce programme dans le c et les vars sont traités et réglés correctement, il finira regarder quelque chose comme ceci:
((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
Y a-t-il des bibliothèques utiles là-bas pour évaluer les expressions qui sont représentés comme une chaîne comme celui-ci? Je pensais que je pouvais appeler un programme Perl avec la chaîne comme un argument qui serait en mesure de retourner le résultat facilement, mais ne savait pas s'il y avait une bibliothèque en C qui a fait cela, ou s'il y a des algorithmes connus pour résoudre ces expressions?
EDIT: Ce que je suis à la recherche de quelque chose qui crachait une réponse à cette expression, parse était peut-être un mauvais mot. à-dire 1 ou 0
Dans une coquille écrou est un fichier contenant un tas d'expressions aléatoires (déjà connus pour être dans le format) qui doivent être évalués à 0 ou 1. (1 ci-dessus pour évaluer, car il en résulte (1 ET 1 ).
La solution
J'ai essayé d'écrire le code C le plus compact pour ce problème d'évaluation de l'expression bool. Voici mon code final:
EDIT: supprimé
Voici le traitement de négation ajouté:
EDIT: code de test ajouté
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; }
}
}
Test:
#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 );
}
Autres conseils
Vous pouvez intégrer lua dans votre programme, puis l'appeler est interprète pour évaluer l'expression.
Il est assez facile de rouler votre propre analyseur de descente récursive pour les expressions simples comme celles-ci.
Je dispose d'un programme similaire autour de cette outil analyseur récursif décent donc je brosser et ici il 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;
}
Et ceci est un code de test:
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;
}
Ceci est :-D amusant.
Je crois que Lex et Yacc sont toujours le meilleur outils pour les tâches d'analyse simples comme celui-ci.
Il y a quelque temps, je l'ai écrit un évaluateur d'expression complète C (à savoir les expressions évaluées par écrit en utilisant la syntaxe C) pour un processeur de ligne de commande et langage de script sur un système embarqué. Je cette description de l'algorithme comme point de départ. Vous pouvez utiliser le code d'accompagnement directement, mais je n'ai pas aimé la mise en œuvre, et a écrit mon propre de la description de l'algorithme. Il fallait un peu de travail pour soutenir tous les opérateurs C, les appels de fonction et les variables, mais une explication claire et donc un bon point de départ, surtout si vous n'avez pas besoin de ce niveau d'exhaustivité.
Le principe de base est que l'évaluation de l'expression est plus facile pour un ordinateur à l'aide d'une pile et « notation polonaise inversée », de sorte que l'algorithme convertit une expression de notation en correction avec l'ordre associé de préséance et entre parenthèses à RPN, puis évalue par popping opérandes, effectuer des opérations, et en poussant les résultats, jusqu'à ce qu'il n'y a pas d'opérations à gauche et une valeur à gauche sur la pile.
L'écriture d'un analyseur d'expression est facile en principe, mais prend une bonne quantité d'effort.
Voici une base à bas analyseur d'expression descente récursive je l'ai écrit en 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/ analyser / SQL / summary.html package-
Cela peut ne pas être exactement ce que vous cherchez, mais il vous donnera une idée de ce dont vous avez besoin.
