c Ausdruck Evaluator
https://stackoverflow.com/questions/1465909
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
lässt Okay, ich habe eine Zeichenfolge wie diese in einer Textdatei haben:
((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
danach in die c-Programm-Parsing und die Vars behandelt und richtig eingestellt wird schauen, um etwas am Ende wie folgt:
((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
Gibt es nützliche Bibliotheken gibt für Auswerten von Ausdrücken, die als eine Zeichenfolge wie folgt dargestellt werden? Ich dachte, dass ich nur ein Perl-Programm mit der Zeichenfolge als ein Argument nennen könnte, die das Ergebnis leicht zurück wäre in der Lage war aber nicht sicher, ob es eine Bibliothek in C war, der das getan hat, oder wenn es irgendwelche bekannten Algorithmen zur Lösung solche Ausdrücke?
EDIT: Was ich suche eigentlich für etwas, das eine Antwort auf diesen Ausdruck ausspucken würde, vielleicht ein schlechtes Wort war parsen. d 1 oder 0
In einer Nussschale sich eine Datei, die eine Reihe von zufälligen Ausdrücke (bereits bekannt, im richtigen Format zu sein) enthält, die entweder zu bewerten müssen auf 0 oder 1 (auswertet oben zu 1, weil es ergibt sich (1 AND 1 ).
Lösung
Ich habe versucht, den kompakteste C-Code für dieses Bool Ausdrucksauswertung Problem zu schreiben. Hier ist mein letzter Code:
EDIT: entfällt
Hier ist die Negation hinzugefügt Handhabung:
EDIT: Testcode hinzugefügt
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 );
}
Andere Tipps
Sie können einbetten lua in Ihrem Programm und dann rufen Sie es Interpreter ist der Ausdruck ausgewertet werden.
Es ist leicht genug, um Ihre eigene Rekursiver Abstieg für einfache Ausdrücke wie diese.
I hat ähnliches Programm rund um die rekursive anständigen Parser implementieren, damit ich es auffrischen und hier ist es.
#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;
}
Und das ist ein Testcode:
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;
}
Das ist Spaß :-D.
Ich glaube, Lex und Yacc noch sind die besten Werkzeuge für die einfache Analyse Aufgaben wie diese.
Vor einiger Zeit habe ich eine komplette C Ausdrucksauswerter geschrieben (d ausgewertet Ausdrücke mit C-Syntax geschrieben) für eine Befehlszeilenprozessor und Skriptsprache auf einem Embedded-System. I verwenden diese Beschreibung des Algorithmus, der als Ausgangspunkt. Sie könnten den beigefügten Code direkt verwenden, aber ich habe nicht die Umsetzung mag, und schrieben meine eigenen aus der Algorithmus Beschreibung. Es brauchte einige Arbeit, um alle C-Operatoren, Funktionsaufrufe zu unterstützen und Variablen, sondern ist eine klare Erklärung und daher ein guter Ausgangspunkt, vor allem, wenn Sie nicht, dass Niveau der Vollständigkeit benötigen.
Das Grundprinzip besteht darin, dass die Ausdrucksauswertung für einen Computer einfacher ist, einen Stapel und ‚Reverse Polish Notation‘ verwendet, so dass der Algorithmus wandelt einen in-fix Notation Ausdruck mit zugehöriger Rangordnung und Klammern RPN und wertet sie dann durch popping Operationen Operanden, die Durchführung und die Ergebnisse schieben, bis es keine Operationen links und ein Wert links auf dem Stapel ist.
Das Schreiben eines Ausdrucksparser ist im Prinzip einfach, aber nimmt eine ganze Menge Aufwand.
Hier ist eine grundlegende zu-down rekursiven Abstieg Ausdrucksparser ich in Java geschrieben: 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/ parsen / sQL / Paket-summary.html
Das ist vielleicht nicht genau das, was Sie suchen, aber es gibt Ihnen eine Vorstellung davon, was Sie brauchen.
