page294.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 60 行
HTML
60 行
<HTML><HEAD><TITLE>Applications</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="tex2html4585" HREF="page295.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4583" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4579" HREF="page293.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4587" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION009680000000000000000">Applications</A></H2><P>Section <A HREF="page144.html#secstacksapps"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how a stack can be usedto compute the value of a postfix expression such as<P><A NAME="eqntreespostfix2"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation16657" SRC="img1155.gif" ><P>Suppose instead of evaluating the expression we are interestedin constructing the corresponding expression tree.Once we have an expression tree,we can use the methods described in Section <A HREF="page263.html#sectreesexprtrees"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>to print out the expression in prefix or infix notation.Thus, we have a means for translating expressions fromone notation to another.<P>It turns out that an expression tree can be constructed fromthe postfix expression relatively easily.The algorithm to do this is a modified version of the algorithmfor evaluating the expression.The symbols in the postfix expression are processedfrom left to right as follows:<OL><LI> If the next symbol in the expression is an operand, a tree comprised of a single node labeled with that operand is pushed onto the stack.<LI> If the next symbol in the expression is a binary operator, the top two trees in the stack correspond to its operands. Two trees are popped from the stack and a new tree is created which has the operator as its root and the two trees corresponding to the operands as its subtrees. Then the new tree is pushed onto the stack.</OL>After all the symbols of the expression have been processed in this fashion,the stack will contain a single treewhich is the desired expression tree.Figure <A HREF="page294.html#figtree10"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the use of a stackto construct the expression tree from the postfix expressiongiven in Equation <A HREF="page294.html#eqntreespostfix2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="17161"> </A><A NAME="figtree10"> </A> <IMG WIDTH=575 HEIGHT=720 ALIGN=BOTTOM ALT="figure16674" SRC="img1156.gif" ><BR><STRONG>Figure:</STRONG> Postfix to infix conversion using a stack of trees.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html4588" HREF="page295.html#SECTION009681000000000000000">Implementation</A></UL><HR><A NAME="tex2html4585" HREF="page295.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4583" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4579" HREF="page293.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4587" 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 + -
显示快捷键?