如何在C语言中编写布尔表达式计算器? [英] How to Write a Boolean Expression Evaluator in C?

问题描述

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

 (((((var1 AND var2 AND var3)OR var4)AND(((var5 OR var6)AND var7))) 

将其解析到C程序中并正确处理并设置了var后，最终将看起来像这样:

 ((((1 AND 0 AND 0)OR 1)AND((0 OR 1)AND 1)) 

有没有有用的库可以用来评估像这样一个字符串表示的表达式?我当时以为我可以使用该字符串作为参数调用Perl程序，从而可以轻松返回结果，但是我不确定C中是否有执行此操作的库，或者是否有任何已知的算法解决这样的表达?

我实际上正在寻找的东西会吐出这个表达式的答案(也许解析是一个坏词)，即1或0.

简而言之，它是一个文件，其中包含一堆随机表达式(已知格式正确)，需要将其评估为0或1.(上述示例的评估结果为1，因为其结果为(1AND 1)).

解决方案

我尝试针对此布尔表达式评估问题编写最紧凑的C代码.这是我的最终代码:

已删除

这是添加的否定处理:

添加了测试代码

  char * eval(char * expr，int * res){枚举{LEFT，OP1，MID，OP2，RIGHT} state = LEFT;枚举{AND，OR} op;int mid = 0，tmp = 0，NEG = 0；for(;; expr ++，state ++，NEG = 0){for(;; expr ++)if(* expr =='！')NEG =！NEG;否则if(* expr！='')中断；if(* expr =='0'){tmp = NEG;}否则if(* expr =='1'){tmp =！NEG;}否则if(* expr =='A'){op = AND;expr + = 2;}否则if(* expr =='&'){op = AND;expr + = 1;}否则if(* expr =='O'){op = OR;expr + = 1;}否则if(* expr =='|'){op = OR;expr + = 1;}否则if(* expr =='('){expr = eval(expr + 1，&tmp); if(NEG)tmp =！tmp;}否则if(* expr =='\ 0'||* expr ==')'){if(state == OP2)* res | = mid;return expr;}if(state == LEFT){* res = tmp;}否则if(state == MID && op == OR){mid = tmp;}否则if(state == MID && op == AND){* res&= tmp;状态=左；}否则if(state == OP2 && op == OR){* res | = mid;状态= OP1;}否则if(state == RIGHT){mid&= tmp;状态= MID;}}} 

测试:

  #include< stdio.h>无效测试(char * expr，int exprval){结果eval(expr，&result);printf("expr:'％s'result:％i％s \ n"，expr，result，result == exprval?"OK":"FAILED");}#定义TEST(x)测试(#x，x)#define AND &&#define或||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);} 

Suppose I have a string such as this in a text file:

(((var1 AND var2 AND var3) OR var4) AND ((var5 OR var6) AND var7))

After parsing this into the C program and the vars are handled and set correctly it will end up looking something like this:

(((1 AND 0 AND 0) OR 1) AND ((0 OR 1) AND 1))

Are there any useful libraries out there for evaluating expressions that are represented as one string like this? I was thinking I could just call a Perl program with the string as an argument that would be able to return the result easily, but I wasn't sure if there was a library in C that did this, or if there are any known algorithms for solving such expressions?

What I'm actually looking for is something that would spit out an answer to this expression (maybe parse was a bad word) i.e. 1 or 0.

In a nutshell, it's a file containing a bunch of random expressions (already known to be in the right format) that need to be evaluated to either 0 or 1. (The example above evaluates to 1 because it results in (1 AND 1)).

解决方案

I tried to write the most compact C code for this bool expression evaluation problem. Here is my final code:

EDIT: deleted

Here is the added negation handling:

EDIT: test code added

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;  }
  }
}

Testing:

#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 );
}

这篇关于如何在C语言中编写布尔表达式计算器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！