parsing math expression in c++

I have a question about Parsing Trees:

I have a string (math expresion estring), for example: (a+b)*c-(d-e)*f/g. I have to parse that expression in a Tree:

class Exp{};
class Term: public Exp{
    int n_;
}

class Node: Public Exp{
    Exp* loperator_;
    Exp* roperator_;
    char operation; // +, -, *, /
}

What algorithm can I use to build a tree which represents the expresion string above?

Solution 1:

Use the Shunting-yard algorithm. The wikipedia description is quite comprehensive, I hope it will suffice.

You can also try to write a formal grammar, for example a parsing-expression grammar, and use a tool to generate a parser. This site about PEGs lists 3 C/C++ libraries for PEG parsing.

Solution 2:

(a+b)*c-(d-e)*f/g is an in-fix expression.

To easily make a tree, convert that into a Prefix expression first.

From the Example, prefix of (A * B) + (C / D) is + (* A B) (/ C D)

     (+)            
     / \        
    /   \       
  (*)    (/)         
  / \   /  \        
 A   B C    D   

 ((A*B)+(C/D))  

Your tree then looks has + as its root node. You can continue populating the left and right sub-tree, about each operator.

Also, this link explains Recursive Descent Parsing in detail, and can be implemented.