evaluate - 如何用 C 编写 bool 表达式求值器？

Question

假设我在文本文件中有这样一个字符串:

(((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)).

Answer 1

我试图为这个 bool 表达式求值问题编写最紧凑的 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 );
}