Building expression tree

Given a expression like 4 * 5 + 9, how can we build a expression tree out of this?

I was reading this interview question on job portal and thought of trying it.

The problem is if this had been parenthesized, it would had been little easier to build

For example ((4 * 5) + 9).

Then with the opening of left parenthesis, we 开发者_Go百科would know we have to go left, wherein the number would be a leaf node and operator would be parent, and once we hit right parenthesis, we would return and go up the level.

How can we build such expression trees?

you can start with BNF and work your way to the tree. in case of simple expressions with parenthesis that would be

 EXPR ::= TERM [ ('+'|'-') TERM ]
 TERM ::= MUL [ ('*'|'/') MUL ]
 MUL ::= NUMBER | '(' EXPR ')'
 NUMBER ::= DIGIT [ DIGIT ]
 DIGIT ::= '0' ... '9'

just write the functions to parse each part (or use boost::spirit) and you will get your tree