CODEWITHSUNDEEP
expression-trees
daydreamer
daydreamer

Reputation: 91999

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 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?

Upvotes: 1

Views: 1325

Answers (1)

DennyRolling
DennyRolling

Reputation: 486

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

Upvotes: 2

Related Questions