c espressione Evaluator
https://stackoverflow.com/questions/1465909
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Consente Va bene dire che ho una stringa come questa in un file di testo:
((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
Dopo l'analisi di questo nel programma c ei Vars sono gestite e impostare correttamente finirà per guardare qualcosa di simile:
((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
Ci sono utili librerie là fuori per la valutazione di espressioni che sono rappresentati come una stringa come questa? Stavo pensando che potrei chiamare un programma Perl con la stringa come un argomento che sarebbe in grado di restituire il risultato facilmente, ma non era sicuro se ci fosse una libreria in C che ha fatto questo, o se ci sono algoritmi noti per la risoluzione tali espressioni?
EDIT: Quello che sto effettivamente cercando è qualcosa che avrebbe sputato fuori una risposta a questa espressione, forse analisi sintattica è stata una brutta parola. cioè 1 o 0
In un guscio di noce è un file contenente un gruppo di espressioni casuali (già noti per essere nel formato corretto) che devono essere valutati a 0 o 1. (sopra restituisce 1 perché comporta (1, 1 ).
Soluzione
Ho provato a scrivere il codice C più compatta per questo problema bool valutazione dell'espressione. Qui è il mio codice finale:
EDIT: soppresso
Questa è la manipolazione negazione aggiunto:
EDIT: il codice di prova aggiunto
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 );
}
Altri suggerimenti
È possibile incorporare lua nel programma e quindi richiamare è interprete per valutare l'espressione.
E 'abbastanza facile da rotolare il proprio ricorsiva discesa parser per espressioni semplici come questi.
I dispone di un programma simile in giro che implementano parser ricorsivo-decente quindi mi lavo su e qui lo è.
#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 questo è un codice di prova:
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;
}
Questa è divertente :-D.
Lex e Yacc sono ancora il migliore strumenti per semplici compiti di analisi di questo tipo.
Qualche tempo fa, ho scritto un completo analizzatore di espressioni C (ovvero le espressioni valutate scritti utilizzando la sintassi C) per un processore riga di comando e linguaggio di script su un sistema embedded. Ho usato questa descrizione dell'algoritmo come punto di partenza. È possibile utilizzare il codice che accompagna direttamente, ma non mi piaceva l'attuazione, e scrisse il mio dalla descrizione dell'algoritmo. E 'necessario un lavoro per sostenere tutti gli operatori C, chiamate di funzione e le variabili, ma è una spiegazione chiara e quindi un buon punto di partenza, soprattutto se non hai bisogno di quel livello di completezza.
Il principio di base è che la valutazione delle espressioni è più facile per un computer che utilizza uno stack e 'notazione polacca inversa', quindi l'algoritmo converte un'espressione notazione in-fix con ordine associato di precedenza e le parentesi per RPN, e poi lo valuta da popping operandi, eseguire operazioni, e spingendo risultati, finché non ci sono operazioni sinistra e un valore lasciati in pila.
Scrivere un parser di espressioni è facile in linea di principio, ma richiede una buona dose di sforzo.
Ecco una base ricorsiva-discesa espressione parser per-down che ho scritto in 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/ analizzare / SQL / package-summary.html
Questo non può essere esattamente quello che stai cercando, ma vi darà un'idea di che cosa avete bisogno.
