page295.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 60 行
HTML
60 行
<HTML>
<HEAD>
<TITLE>Applications</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html5570" HREF="page296.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page296.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5568" HREF="page266.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page266.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5564" HREF="page294.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page294.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5572" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5573" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0010680000000000000000">Applications</A></H2>
<P>
Section <A HREF="page144.html#secstacksapps" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page144.html#secstacksapps"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows how a stack can be used
to compute the value of a postfix expression such as
<P><A NAME="eqntreespostfix2"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation17361" SRC="img1206.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1206.gif" ><P>
Suppose instead of evaluating the expression we are interested
in constructing the corresponding expression tree.
Once we have an expression tree,
we can use the methods described in Section <A HREF="page262.html#sectreesexprtrees" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page262.html#sectreesexprtrees"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
to print out the expression in prefix or infix notation.
Thus, we have a means for translating expressions from
one notation to another.
<P>
It turns out that an expression tree can be constructed from
the postfix expression relatively easily.
The algorithm to do this is a modified version of the algorithm
for evaluating the expression.
The symbols in the postfix expression are processed
from 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 tree
which is the desired expression tree.
Figure <A HREF="page295.html#figtree10" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page295.html#figtree10"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrates the use of a stack
to construct the expression tree from the postfix expression
given in Equation <A HREF="page295.html#eqntreespostfix2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page295.html#eqntreespostfix2"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="17872"> </A><A NAME="figtree10"> </A> <IMG WIDTH=575 HEIGHT=718 ALIGN=BOTTOM ALT="figure17378" SRC="img1207.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1207.gif" ><BR>
<STRONG>Figure:</STRONG> Postfix to Infix Conversion using a Stack of Trees<BR>
<P><BR> <HR>
<UL>
<LI> <A NAME="tex2html5574" HREF="page296.html#SECTION0010681000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page296.html#SECTION0010681000000000000000">Implementation</A>
</UL>
<HR><A NAME="tex2html5570" HREF="page296.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page296.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5568" HREF="page266.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page266.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5564" HREF="page294.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page294.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5572" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5573" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?