c expression Evaluator

Question

Okay lets say 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 wasn't sure if there was a library in C that did this, or if there are any known algorithms for solving such expressions?

EDIT: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 nut shell its 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. (above evaluates to 1 because it results in (1 AND 1).

Answer 1

You can embed lua in your program and then invoke it's interpreter to evaluate the expression.

Answer 2

I believe Lex and Yacc are still the best tools for simple parsing tasks like this.

Answer 3

It's easy enough to roll your own recursive descent parser for simple expressions like these.

Answer 4

Writing an expression parser is easy in principle, but takes a fair amount of effort.

Here's a basic to-down recursive-descent expression parser I wrote in Java: 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/parse/sql/package-summary.html

This may not be exactly what you're looking for, but it will give you an idea of what you need.

Answer 5

A while ago, I wrote a complete C expression evaluator (i.e. evaluated expressions written using C syntax) for a command line processor and scripting language on an embedded system. I used this description of the algorithm as a starting point. You could use the accompanying code directly, but I did not like the implementation, and wrote my own from the algorithm description. It needed some work to support all C operators, function calls, and variables, but is a clear explanation and therefore a good starting point, especially if you don't need that level of completeness.

The basic principle is that expression evaluation is easier for a computer using a stack and 'Reverse Polish Notation', so the algorithm converts a in-fix notation expression with associated order of precedence and parentheses to RPN, and then evaluates it by popping operands, performing operations, and pushing results, until there are no operations left and one value left on the stack.

Answer 6

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