Cの式エバリュエータ
https://stackoverflow.com/questions/1465909
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
オーケー、私はこのような文字列を持って言うことができますテキストファイルます：
((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
Cプログラムにこれを解析しVARSが、それはこのような何かを探してしまいます取り扱われ、正しく設定されている後：
((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
任意の有用なライブラリは、このような1つの文字列として表現されている式を評価するためにそこにありますか？私はちょうどこれをしなかったCでライブラリがあった場合、簡単に結果を返すことができますが確認されませんでしたでしょう引数として文字列をPerlプログラムを呼び出すことができます考えていた、または解決するための任意の既知のアルゴリズムがある場合このような式？
編集：どのような私が実際に探していますが、この式の答えを吐き出す何かである、多分解析は、悪い言葉でした。すなわち、1または0
ナットにおいては、（1,1もたらすので、0または1のいずれかに評価する必要がランダム式の束を含むファイルが（すでに適切なフォーマットであることが知られている）（上記1に評価のシェル）。
解決
私は、このブール式の評価の問題のための最もコンパクトなCコードを記述しようとしました。ここに私の最終的なコードがあります：
編集：削除
ここで追加否定取り扱いがあります：
編集：テストコードを追加
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; }
}
}
テスト
#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 );
}
他のヒント
あなたはあなたのプログラムに LUA に埋め込み、それが式を評価するために、インタプリタだ呼び出すことができます。
これは、これらのような単純な式のために独自の再帰下降構文解析を巻くだけ簡単です。
私はそれをブラッシュアップし、ここにあるように、その周囲に同様のプログラムが再帰まともなパーサを実装しています。
タグ
#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;
}
これはテストコードです：
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;
}
この楽しい:-Dです。
私は信じているまだ最高ですのLexとYaccのこのような単純な構文解析タスクのためのツール。
Aしばらく前に、私は、組み込みシステムのコマンドラインプロセッサおよびスクリプト言語のために（すなわち、C構文を使用して記述された式を評価した）完全なCの発現評価を書きました。 Iは、出発点として、アルゴリズムのこのの記述を使用します。あなたは直接付随するコードを使用することができますが、私は実装を好きではなかった、とアルゴリズムの記述から私自身を書きました。それはあなたが完全にそのレベルを必要としない場合は特に、すべてのC演算子、関数呼び出し、および変数をサポートするためにいくつかの作業を必要としますが、明確な説明とそのための良い出発点である。
の基本的な原理は、式の評価は、スタックと「逆ポーランド記法」を使用してコンピュータのが容易であるので、アルゴリズムはRPNの優先順位と括弧の関連順序でフィックス表記表現に変換し、次にによって、それを評価することです、オペランドをポップ動作を実行し、何も操作が残っていないと一つの値がスタックに残されるまで、結果を押します。
表現パーサーを書くのは原理的には簡単ですが、努力のかなりの量をとります。
ここで私はJavaで書いた基本的にダウン再帰下降式パーサーです： http://david.tribble.com/src/java/トリブル/パース/ SQL / QueryParser.javaする http://david.tribble.com/src/java/トリブル/パース/ SQL / ExprLexer.javaする http://david.tribble.com/src/java/トリブル/パース/ SQL / ExprLexer.javaする http://david.tribble.com/docs/tribble/パース/ SQL /パッケージ-summary.htmlにする
これは、あなたが探している正確に何ではないかもしれないが、それはあなたが必要なもののアイデアを与えるだろう。
