How to parse a formula from a string?

Question

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?

Sorry, but what is exactly being done by `parse_formula()` that cannot be done the _usual_ way? — Sourav Ghosh, Feb 11 '15 at 09:17
@SouravGhosh he is looking for a library to do the parsing of the function to a value. — Christo S. Christov, Feb 11 '15 at 09:17
Mr @Chris something like `double result = ((data1 + data2) ^ data3) / data4` or am I missing something? — Sourav Ghosh, Feb 11 '15 at 09:19
@SouravGhosh Imagine if the formula string was entered at runtime. — unwind, Feb 11 '15 at 09:20
parse_formula() should parse formula string, get data values by name (for example by using uthash), calculate the result and return double. — J. Leeroy, Feb 11 '15 at 09:20
Nope, I don't think it is. Look at Reverse Polish Notation and implement it yourself. It's both educational and entertaining. I implemented such parser in Pascal and learned a lot from this. — zubergu, Feb 11 '15 at 09:20
Possible duplicate of [Evaluate Mathematical Function from String](https://stackoverflow.com/questions/9977045/evaluate-mathematical-function-from-string) — Baum mit Augen, Aug 27 '17 at 23:26
Parsing is a very large subject. I suggest you google for more information about it. — Code-Apprentice, Aug 27 '17 at 23:31
Note that the string in your example does not contain the numerical values of any of the variables. — Code-Apprentice, Aug 27 '17 at 23:31

score 3 · Accepted Answer · edited May 23 '17 at 12:21

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

I don't consider this to be the right answer. The question specifically asked if there was available a C library that could parse and evaluate an expression. The questioner didn't ask if there was something in the standard library, just whether such a library exists anywhere. The answer is obviously yes. Yes one can learn a lot by implementing your own parser and evaluator but this is not what the questioner asked for. — rhody, Aug 27 '17 at 18:47
@rhody Note that the OP also asked "Or what is the best way to code it by myself?". However, if you would like to share libraries which may be useful, feel free to add an answer. — Frerich Raabe, Aug 27 '17 at 19:22

score 2 · Answer 2 · answered Feb 11 '15 at 09:21

There is no such function in the standard library, no.

There are any number of libraries, I'm not going to recommend one here.

Note that no library will allow "automatic" access by name to your program's variables; they are not available at runtime. You're going to have to find an expression evaluator with variable support, and initialize the variables in the evaluator before trying to evaluate the formula itself.

score 0 · Answer 3 · answered Aug 27 '17 at 18:43

There are quite a number of parsers available, both in C++ and plain C. For C++ there is muParser:

http://beltoforion.de/article.php?a=muparser&hl=en&s=idPageTop#idPageTop

For C I found this little one which looks promising:

https://github.com/codeplea/tinyexpr

How to parse a formula from a string?

3 Answers3

Linked