This is not the document you are looking for? Use the search form below to find more!
asdf
0.00 (0 votes)
Document Description
sadf
File Details- Added: March, 02nd 2012
- Reads: 78
- Downloads: 0
- File size: 83.77kb
- Pages: 2
- content preview
- Name: asdf
Embed Code:
Related Documents
Content Preview
ExpressionsTrees
Compilersneedtogeneratemachinecodeinwhichoneoperandisexecutedatatime.All
expressionshavetobebrokendownunambiguouslyintoseparateoperationsandputintotheir
properorder.Toachievethis,compilersusepostfixnotation.However,humansuseinfixnotation
whichisambiguousunlessbracketsareused.
Leavescontainoperands(constantsorvariables).Innernodescontainoperators.
BuildinganExpressionTreefromaPostfixExpression
Postfixnotationallowsforthecreationofanexpressiontree,whichimposesanorderonthe
executionofoperations.
Algorithm
Scantheexpressionfromlefttoright.
Ifthesymbolisanoperand,createaonenodetreeforitandpushitontothestack.
Ifthesymbolisanoperator,poptwotreesT1andT2.
MergeT1andT2,usingthesymbolastherootnodeandmakingthefirsttreepoppedtherightchild
andthesecondtheleftchild
Pushthenewlymergedtreeontothestack.
Example
Buildatreefromtheexpressionab+cde+**
2.ab+cde+**
1.ab+cde+**
3.ab+cde+**
4.ab+cde+**
5.ab+cde+**
6.ab+cde+**DONE!
Assignment
1.Givenapostfixexpression,buildatreeforit
2.Verifythecorrectnessofthetreebyoutputtingthepostfixexpressionusedtobuildit.
3.Outputtheinfixexpressionrepresentedbythetree,buteliminateambiguities.
Compilersneedtogeneratemachinecodeinwhichoneoperandisexecutedatatime.All
expressionshavetobebrokendownunambiguouslyintoseparateoperationsandputintotheir
properorder.Toachievethis,compilersusepostfixnotation.However,humansuseinfixnotation
whichisambiguousunlessbracketsareused.
Leavescontainoperands(constantsorvariables).Innernodescontainoperators.
BuildinganExpressionTreefromaPostfixExpression
Postfixnotationallowsforthecreationofanexpressiontree,whichimposesanorderonthe
executionofoperations.
Algorithm
Scantheexpressionfromlefttoright.
Ifthesymbolisanoperand,createaonenodetreeforitandpushitontothestack.
Ifthesymbolisanoperator,poptwotreesT1andT2.
MergeT1andT2,usingthesymbolastherootnodeandmakingthefirsttreepoppedtherightchild
andthesecondtheleftchild
Pushthenewlymergedtreeontothestack.
Example
Buildatreefromtheexpressionab+cde+**
2.ab+cde+**
1.ab+cde+**
3.ab+cde+**
4.ab+cde+**
5.ab+cde+**
6.ab+cde+**DONE!
Assignment
1.Givenapostfixexpression,buildatreeforit
2.Verifythecorrectnessofthetreebyoutputtingthepostfixexpressionusedtobuildit.
3.Outputtheinfixexpressionrepresentedbythetree,buteliminateambiguities.
Add New Comment