Talk:Binary expression tree
|WikiProject Computer science||(Rated Start-class, Low-importance)|
|This article is the subject of an educational assignment at College Of Engineering Pune supported by Wikipedia Ambassadors through the India Education Program during the 2011 Q3 term. Further details are available on the course page.|
The input is: a b + c d e + * *
Since the first two symbols are operands, one-node trees are created and pointers are pushed to them onto a stack. For convenience the stack will grow from left to right.
The next symbol is a '+'. It pops the two pointers to the trees, a new tree is formed, and a pointer to it is pushed onto to the stack.
Next, c, d, and e are read. A one-node tree is created for each and a pointer to the corresponding tree is pushed onto the stack.
Continuing, a '+' is read, and it merges the last two trees.
Now, a '*' is read. The last two tree pointers are popped and a new tree is formed with a '*' as the root.
Finally, the last symbol is read. The two trees are merged and a pointer to the final tree remains on the stack.