page295.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 108 行
HTML
108 行
<HTML><HEAD><TITLE>Implementation</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html4595" HREF="page296.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4593" HREF="page294.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4589" HREF="page294.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4597" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION009681000000000000000">Implementation</A></H3><P>Program <A HREF="page295.html#progexpressionTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the <tt>ExpressionTree</tt> class.This class provides a static method,called <tt>parsePostfix</tt>,which translates a postfix expression to an infix expressionusing the method described above.This method reads an expression from the input streamone word at a time.The expression is assumed to be a syntactically validpostfix expression comprised ofnumbers, variables,and the binary operators <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, and <tt>/</tt>,each separated by blank space.<P><P><A NAME="17175"> </A><A NAME="progexpressionTreea"> </A> <IMG WIDTH=575 HEIGHT=428 ALIGN=BOTTOM ALT="program17172" SRC="img1157.gif" ><BR><STRONG>Program:</STRONG> Binary tree application--postfix to infix conversion.<BR><P><P>Since only binary operators are allowed,the resulting expression tree is a binary tree.Consequently,the <tt>ExpressionTree</tt> class extends the <tt>BinaryTree</tt> classintroduced in Program <A HREF="page287.html#progbinaryTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>The main program loop, lines 9-18,reads words from the input stream one at a time.If an operator is found,a new tree is created with the operator as its root (line 13).Next, two trees are popped from the stackand attached to the new tree which is then pushed onto the stack(lines 14-15).Otherwise, the input word is taken to be an argument.A new expression tree with that argument at its root is createdand pushed onto the stack (line 18).<P>When the <tt>parsePostfix</tt> method encounters the end-of-file,its main loop terminates.The resulting expression tree is popped from the stack and returnedfrom the <tt>parsePostfix</tt> method (line 19).<P>Program <A HREF="page295.html#progexpressionTreeb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>__str__</tt> methodfor the <tt>ExpressionTree</tt> class.This method can be used to print out the expressionrepresented by the tree.<P><P><A NAME="17193"> </A><A NAME="progexpressionTreeb"> </A> <IMG WIDTH=575 HEIGHT=485 ALIGN=BOTTOM ALT="program17190" SRC="img1158.gif" ><BR><STRONG>Program:</STRONG> Binary tree application--printing infix expressions.<BR><P><P>The <tt>__str__</tt> method constructs a string that representsthe expression using an <tt>InfixVisitor</tt>which does a depth-first traversaland accumulates its result in string like this:At each non-terminal node of the expression tree,the depth-first traversal first calls <tt>preVisit</tt>,which appends a left parenthesis to the string.In between the traversals of the left and right subtrees,the <tt>inVisit</tt> method is called,which appends a textual representation of the object contained within the nodeto the string.Finally, after traversing the right subtree,<tt>PostVisit</tt> appends a right parenthesis to the string.Given the input <tt>ab/cd-e*+</tt>,the program constructs the expression tree as shown in Figure <A HREF="page294.html#figtree10"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,and then forms the infix expression<P> <IMG WIDTH=363 HEIGHT=13 ALIGN=BOTTOM ALT="displaymath63625" SRC="img1159.gif" ><P><P>The running time of the <tt>parsePostfix</tt> method depends uponthe number of symbols in the input.The running time for one iteration the main loop is <I>O</I>(1).Therefore, the time required to construct the expression treegiven <I>n</I> input symbols is <I>O</I>(<I>n</I>).The <tt>depthFirstTraversal</tt> methodvisits each node of the expression tree exactly onceand a constant amount of work is required to print a node.As a result, printing the infix expression is also <I>O</I>(<I>n</I>)where <I>n</I> is the number of input symbols.<P>The output expression contains all of the input symbolsplus the parentheses added by the <tt>__str__</tt> method.It can be shown that a valid postfix expression that contains <I>n</I> symbols,always has (<I>n</I>-1)/2 binary operators and (<I>n</I>+1)/2 operands(Exercise <A HREF="page296.html#exercisetreespostfix"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).Hence, the expression tree contains (<I>n</I>-1)/2 non-terminal nodesand since a pair of parentheses is added for each non-terminal nodein the expression tree,the output string contains 2<I>n</I>-1=<I>O</I>(<I>n</I>) symbols altogether.Therefore, the overall running time needed to translatea postfix expression comprised of <I>n</I> symbols to an infix expression is <I>O</I>(<I>n</I>).<P><HR><A NAME="tex2html4595" HREF="page296.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4593" HREF="page294.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4589" HREF="page294.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4597" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?