How to parse expressions in C++

Question

I want to parse expressions such as res = ((a*(2+b))/c)+5.603+(6*(d^5)). I want to do it in c++ only.

Kursk

You might want to look into Boost's Spirit library. – Dagley

Or boost regex lib. Or you need to do it without any 3rd party libs? – Nog

I have never used boost, but thanks for reply. – Kursk

Can anyone name some third party libs except boost – Kursk

I dont understand why when you've been given a solution, i.e. Boost, you reject it and ask for an alternative - what is stopping you from using Boost ? – Sighted

If you want to do this old school, use Lex and Yacc (Flex and Bison). – Dayan

@Kiril, you can't parse such expressions with regex. Regex doesn't allow for recursive definitions. – Pulmonate

may be I am scared of boost as I have not used it earlier. Once I tried to use boost on windows with mingw and I just messed up things. – Kursk

It's certainly true that you don't need boost to parse this. If you don't feel comfortable with boost then don't use it for this; but when you're feeling a bit adventurous, check boost out again. It has so many nice and useful features, it's worth keeping an option. – Gaultiero

There is a ready expression parser in AXE (tinyurl.com/3o4hka7), but you need a C++0x compiler. – Gough

Answer 1

Have a look at the "Available C++ Libraries" FAQ

Crustal

I should declare an interest - I maintain this FAQ, have done for years. – Crustal

Answer 2

Stroustrup explains how you'd evaluate expressions like ((1*(2+3))/4)+5.603+(6*(11^5)). Basically, you build an evaluation tree for all subexpressions.

Your example has three extra steps. In parsing, you have to note the variables a, and in evaluating you have to replace the variables with their current values. Finally, you need to assign the result to variables.

You can use a std::map<std::string, double> to hold the variable names and values.

Inset

an algorithm would be much appreciated – Ferrer

Algorithm for what? The algorithm how to parse (interpret) an expression like 45+12*7 is basic math; each kid learns how to parse that. Evaluating it is also elementary. Parsing a+12*7 is not that much harder, and evaluating it with a=45 is also straightforward. – Inset

Answer 3

There is a thorough treatment of a possible approach to here:

http://www.ibm.com/developerworks/library/j-w3eval/index.html

The code is in java, but is quite portable to C++.

Gaultiero