dump.xml

 
<pdf2xml> 
<meta name="Author" content="Shivashis"/> 
<meta name="Creator" content="Microsoft® Office Word 2007"/> 
<meta name="Producer" content="Microsoft® Office Word 2007"/> 
<meta name="CreationDate" content="20100408180658"/> 
<page t="0" l="0" w="612" h="792"> 
 <text l="260" t="62" w="91" h="18" p="260,78,342,9">PROGRAM 4</text> 
 <text l="72" t="97" w="468" h="13" p="72,25,107,76,193,63,266,37,313,21,344,38,391,12,414,20,444,6,460,38,508,32">This programming assignment carries 200 points, so this a double credit</text> 
 <text l="72" t="113" w="468" h="13" p="72,67,146,12,165,20,192,76,276,63,346,21,374,22,403,29,439,25,471,35,514,26">assignment. In this programming assignment you will work with linked lists,</text> 
 <text l="72" t="129" w="468" h="13" p="72,36,112,30,147,20,172,38,214,29,248,47,300,27,331,24,360,6,370,26,401,77,483,57">binary trees, and stacks. Your program shall read a fully parenthesized arithmetic</text> 
 <text l="72" t="145" w="468" h="13" p="72,63,143,20,170,29,206,6,219,36,262,60,329,21,357,16,380,17,405,29,441,63,511,29">expression, and build a binary expression tree for the input expression. Then</text> 
 <text l="72" t="161" w="468" h="13" p="72,45,122,6,133,58,195,48,248,12,265,17,287,60,351,21,377,20,402,36,443,17,465,60,529,11">perform a post-order traversal of the expression tree and output the expression in</text> 
 <text l="72" t="177" w="468" h="13" p="72,35,113,44,162,49,217,38,260,45,311,6,323,58,386,48,440,12,458,17,480,60">Polish post-fix notation. Again, perform a post-order traversal of the expression</text> 
 <text l="72" t="193" w="468" h="13" p="72,21,102,20,131,47,186,17,211,60,280,20,309,26,344,14,367,70,445,40,493,26,527,13">tree and evaluate the expression and print all intermediate values. That is,</text> 
 <text l="72" t="210" w="468" h="13" p="72,54,132,21,158,47,210,13,228,57,290,26,321,17,344,30,379,54,439,14,458,20,484,56">whenever you evaluate an operation, print the value generated by this operation.</text> 
 <text l="72" t="226" w="468" h="13" p="72,27,104,14,122,29,156,70,230,36,270,14,289,20,313,21,339,53,396,14,415,39,458,29,492,26,523,17">Print all these intermediate values on one line separated by comas. Then print the</text> 
 <text l="72" t="242" w="468" h="13" p="72,26,102,30,137,12,153,17,174,60,238,11,254,6,264,23,292,25,321,31,356,19,379,6,390,29,423,11,438,47,489,20,513,26">final value of the expression in a new line. Next, use a stack to evaluate and print</text> 
 <text l="72" t="258" w="468" h="13" p="72,17,95,35,136,44,186,60,252,64,323,11,340,17,363,48,417,26,450,38,494,26,526,14">the Polish post-fix expression constructed in the previous step. Again, print all</text> 
 <text l="72" t="274" w="468" h="13" p="72,70,147,36,188,20,214,17,236,26,267,30,303,11,319,17,342,29,376,23,405,12,422,39,466,51,523,17">intermediate values and the final value in the same way as before. Compare the</text> 
 <text l="72" t="287" w="468" h="16" p="72,39,117,26,148,30,185,12,202,17,225,60,291,25,322,17,345,48,399,26,431,34,471,27,504,36">second final value of the expression with the previous final value. Print “value</text> 
 <text l="72" t="303" w="468" h="16" p="72,44,120,11,136,13,154,45,204,12,220,6,231,39,275,51,331,12,347,17,369,29,403,69,476,16,497,19,521,19">verified to be correct” or a similar message. In the input expressions, we use “$”</text> 
 <text l="72" t="319" w="233" h="16" p="72,16,92,83,179,33,215,24,242,29,275,30">for exponentiation rather than usual “**”.</text> 
 <text l="76" t="348" w="465" h="13" p="76,48,127,7,138,9,151,20,175,56,235,30,268,18,289,10,303,25,331,26,361,30,395,11,409,26,438,37,479,26,509,31">Program 4 is due Thursday, April 29, at 1:00 AM. Hand in your source code (.f95)</text> 
 <text l="72" t="365" w="468" h="13" p="72,19,94,20,118,17,139,36,179,19,201,93,298,79,381,20,405,30,438,6,448,31,483,27,513,12,529,11">file and the output file (Expression.out) electronically, and bring a paper copy of to</text> 
 <text l="72" t="381" w="96" h="13" p="72,27,103,11,117,17,138,31">hand in the class.</text> 
 <text l="72" t="411" w="122" h="14" p="72,36,112,83">INPUT EXPRESSIONS:</text> 
 <text l="90" t="445" w="157" h="14" p="90,11,108,139">1. ((5+4)+(3/(4$(3-(9/8)))))</text> 
 <text l="90" t="462" w="189" h="14" p="90,11,108,171">2. ((((5+3)/4)$2)+(((5-3)$2)/4))))</text> 
 <text l="90" t="479" w="280" h="14" p="90,11,108,262">3. ((15-(2$($(12-(5*2)))))+(((((15-3)/6)$2)*4)/8))</text> 
 <text l="90" t="514" w="198" h="14" p="90,43,136,40,179,17,199,23,226,63">Sample output for first expression</text> 
 <text l="108" t="547" w="116" h="13" p="108,41,153,71">Postfix Expression:</text> 
 <text l="288" t="544" w="129" h="16" p="288,89,384,0,391,26">54+34398/ ̶ $/+</text> 
 <text l="108" t="563" w="126" h="13" p="108,78,189,45">Intermediate Values:</text> 
 <text l="288" t="563" w="84" h="13" p="288,11,302,11,316,11,330,18,351,11,365,7">9, 1, 2, 16, 0, 9</text> 
 <text l="108" t="579" w="92" h="13" p="108,31,143,32,178,22">Final value V1:</text> 
 <text l="288" t="579" w="7" h="13" p="288,7">9</text> 
 <text l="108" t="595" w="126" h="13" p="108,78,189,45">Intermediate Values:</text> 
 <text l="288" t="595" w="84" h="13" p="288,11,302,11,316,11,330,18,351,11,365,7">9, 1, 2, 16, 0, 9</text> 
 <text l="108" t="612" w="92" h="13" p="108,31,143,32,178,22">Final value V2:</text> 
 <text l="288" t="612" w="7" h="13" p="288,7">9</text> 
 <text l="108" t="644" w="202" h="13" p="108,31,143,37,184,17,204,23,230,17,251,19,274,36">Final values V1 and V2 are equal.</text> 
</page> 
</pdf2xml>