This is an old revision of this page, as edited by Ruud Koot(talk | contribs) at 23:10, 10 October 2011({{IEP assignment|course=Wikipedia:India Education Program/Courses/Fall 2011/Data Structures and Algorithms|university=College Of Engineering Pune|term=2011 Q3}}). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.Revision as of 23:10, 10 October 2011 by Ruud Koot(talk | contribs)({{IEP assignment|course=Wikipedia:India Education Program/Courses/Fall 2011/Data Structures and Algorithms|university=College Of Engineering Pune|term=2011 Q3}})
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science
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.
Stack growing 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.
Formation of a New Tree
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.
Creating One-Node Tree
Continuing, a '+' is read, and it merges the last two trees.
Merging Two Trees
Now, a '*' is read. The last two tree pointers are popped and a new tree is formed with a '*' as the root.
Forming a New Tree with a Root
Finally, the last symbol is read. The two trees are merged and a pointer to the final tree remains on the stack.
Steps to Construct an Expression tree a b + c d e + * *
