Evaluating mathematical expressions

Question

I am looking for an algorithm that I can use to evaluate mathematical expressions. I've seen a few questions on SO that are simmilar but the answers are C#/Delphi or python specific. I need to write the algorithm in C :)

The problem I am trying to solve is given a user input like

3*(2*x + 1)/x

I can evaluate the expression for any value of x.

What algorithms are available to do this? If you would like to suggest a library that already does this, then I would prefer a C library

Thank you

Answer 1

The algorithm you need here is the Shunting Yard Algorithm.

This allows you to convert an in-fix expression into Reverse Polish notation, which is quite simple to evaluate programatically.

The Shunting Yard Algorithm is quite involved, but my experiences is that you can code it up just as its written and it all works - you don't have to go to the trouble of analysing it.

Answer 2

I asked Google for "recursive descent expression parser" (I don't blame you for not knowing what to look for) and found Parsing Expressions by Recursive Descent which provides an introduction to some useful parsing techniques.

Also, the Wikipedia article on Recursive descent parser includes a fairly complete example in C.