J. Leeroy J. Leeroy - 2 months ago 13
C Question

How to parse a formula from a string?

For example, I have string

((data1 + data2) ^ data3) / data4
and I want my little program to get this string and do something like this:

int main(int argc, char **argv) {

double data1 = 1.0;
double data2 = 2.0;
double data3 = 3.0;
double data4 = 4.0;

double result = parse_formula("((data1 + data2) ^ data3) / data4");

printf("Result is %d\n", result);
return 0;
}


Is there such a parser in the standard library? If not, how would I make such a parser myself?

Answer Source

There is nothing ready-made in the standard library for parsing expressions, no. However, it's a nice exercise to roll a parser/evaluator yourself. I don't want to spoil the fun, but here are some thoughts:

The idea is to first parse the input string into some sort of data structure which represents the expression (usually some sort of tree structure) and then 'evaluate' that data structure with some given variable bindings.

The data structure might be a tagged union, something like this:

enum ValueType {
 ConstantValue, VariableValue, Addition, Division
};

struct Value {
  enum ValueType type;

  /* The 'representation' of the value. */
  union {
     int constantValue;
     const char *variableValue;
     struct {
       struct Value *summand1;
       struct Value *summand2;
     } additionValue;
     struct {
       struct Value *dividend;
       struct Value *divisor;
     } divisionValue;
  } repr;
};

For the parsing part, I suggest to read up on 'recursive descent' parsers, which area quite easy to understand and write by hand. The goal is to define a function

Value *parse( const char *s );

which returns a representation for the given string.

The evaluation part is quite straightforward and lends itself to recursion. The goal is to define a function

int eval( const Value *v, ??? bindings );

...where ??? would be some type appropriate for holding variable bindings (e.g. a string to int mapping). Depending on the 'type' of the given value, it will perform the arithmetic operation, e.g.:

int eval( const Value *v, ??? bindings ) {
  switch ( v->type ) {
    case ConstantValue:
      return v->repr.constantValue;
    case Addition:
      return eval( v->repr.additionValue.summand1 ) + eval( v->repr.additionValue.summand2 );
    ...