题
好可以说我有一个字符串,如此在文本文件:
((( var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))
解析这个到c程序和瓦尔进行处理,并设置其正确最终会看起来像这样后:
((( 1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))
是否有任何有用的库外面,用于评估被表示为像这样的字符串表达式?我想我可以只调用一个Perl程序与字符串作为参数,将能够轻松地返回结果,但不知道是否有在C库,这样做,或是否有解决任何已知的算法这样的表达
编辑:什么我其实是在寻找的东西,会吐出一个答案的表情,也许是分析一个坏词。即1或0
在坚果壳其包含一串需要进行评估,以0或1(随机表达式(已经知道是在正确的格式)的文件以上的计算结果为1,因为它导致在(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 在程序中,然后调用它的解释器来计算表达式。
这是很容易推出自己的递归下降解析器像这些简单的表达式。
I具有围绕实现递归体面解析器所以我刷它类似程序,并在这里。
#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 仍然最好工具这样简单解析任务。
前一段,我写了一个完整的C表达式求值的命令行处理器和脚本语言的嵌入式系统上(即,使用C语法书面计算的表达式)。我用算法为起点的此内容描述。你可以直接使用附带的代码,但我不喜欢的实施,写我自己从算法描述。它需要一些工作,以支持所有的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
这可能不是你在寻找什么,但它会给你你需要什么的想法。