📄 page165.html
字号:
<HTML>
<HEAD>
<TITLE>Projects</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="tex2html3939" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html3937" HREF="page130.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page130.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="tex2html3933" HREF="page164.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page164.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="tex2html3941" 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="tex2html3942" 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>
<H1><A NAME="SECTION007500000000000000000">Projects</A></H1>
<P>
<OL><LI>
Enhance the functionality of the RPN calculator given
in Program <A HREF="page146.html#progapp01c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page146.html#progapp01c"><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> in the following ways:
<OL><LI>
Use double-precision, floating-point arithmetic.
I.e., use the <tt>Double</tt> class
defined in Program <A HREF="page116.html#progwrapper2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page116.html#progwrapper2h"><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>.<LI>
Provide the complete repertoire of basic operators:
+, -, <IMG WIDTH=8 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline61394" SRC="img724.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img724.gif" > and <IMG WIDTH=10 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline61564" SRC="img774.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img774.gif" >.<LI>
Add an exponentiation operator and a unary negation operator.<LI>
Add a <em>clear</em> function that empties the operand stack
and a <em>print</em> function that prints out the contents
of the operand stack.
</OL><LI>
Modify Program <A HREF="page146.html#progapp01c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page146.html#progapp01c"><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> so that it accepts expressions
written in <em>prefix</em> (Polish) notation.
<b>Hint</b>: See Exercise <A HREF="page164.html#exercisestacksreverse" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page164.html#exercisestacksreverse"><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>.<LI>
Write a program to convert a <em>postfix</em> expression
into an <em>infix</em> expression using a stack.
One way to do this is to modify the RPN calculator program
given in Program <A HREF="page146.html#progapp01c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page146.html#progapp01c"><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 use a stack of infix expressions.
The expressions can be represented as instances of
the <tt>String</tt> class defined in Program <A HREF="page116.html#progwrapper2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page116.html#progwrapper2h"><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>.
A binary operator should pop two strings from the stack
and then push a string which is formed by concatenating
the operator and its operands in the correct order.
For example,
suppose the operator is <tt>'*'</tt>
and the two strings popped from the stack
are <tt>"(b+c)"</tt> and <tt>"a"</tt>.
Then the result that gets pushed onto the stack
is the string <tt>"a*(b+c)"</tt>.<LI> <A NAME="projectstacksconvert"> </A>
Devise a scheme using a stack to convert an <em>infix</em> expression
to a <em>postfix</em> expression.
<b>Hint</b>:
In a postfix expression operators appear <em>after</em> their operands
whereas in an infix expression
they appear <em>between</em> their operands.
Process the symbols in the prefix expression one-by-one.
Output operands immediately,
but save the operators in a stack until they are needed.
Pay special attention to the precedence of the operators.<LI>
Modify your solution to Project <A HREF="page165.html#projectstacksconvert" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page165.html#projectstacksconvert"><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>
so that it immediately evaluates the infix expression.
I.e., create an <tt>InfixCalculator</tt> routine
in the style of Program <A HREF="page146.html#progapp01c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page146.html#progapp01c"><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>.<LI>
Consider a string of characters, <I>S</I>,
comprised only of the characters
<code>(</code>, <code>)</code>, <code>[</code>, <code>]</code>, <code></code> and <code></code>.
We say that <I>S</I> is balanced if it has one of the following forms:
<UL><LI> <IMG WIDTH=47 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline61570" SRC="img775.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img775.gif" >, i.e., <I>S</I> is the string of length zero,<LI> <IMG WIDTH=75 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61574" SRC="img776.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img776.gif" >,<LI> <IMG WIDTH=75 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline61576" SRC="img777.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img777.gif" >,<LI> <IMG WIDTH=74 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61578" SRC="img778.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img778.gif" >,<LI> <IMG WIDTH=71 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline61580" SRC="img779.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img779.gif" ></UL>
where both <I>T</I> and <I>U</I> are balanced strings,
In other words, for every left parenthesis, bracket or brace,
there is a corresponding right parenthesis, bracket or brace.
E.g., <tt>"{()[()]}"</tt> is balanced, but <tt>"([)]"</tt> is not.
Write a program that uses a stack of characters
to test whether a given string is balanced.
(Use the <tt>Char</tt> class defined in Program <A HREF="page116.html#progwrapper2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page116.html#progwrapper2h"><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>).<LI>
Design and implement a <tt>MultipleStack</tt> class
which provides <IMG WIDTH=42 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61586" SRC="img780.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img780.gif" > stacks in a single container.
The declaration of the class should look something like this:
<PRE>class MultipleStack : public Container
{
// ...
public:
MultipleStack (unsigned int);
void Push (Object&, unsigned int);
Object& Pop (unsigned int);
// ...
};</PRE>
<UL><LI>
The constructor takes a single integer argument
that specifies the number of stacks in the container.<LI>
The <tt>Push</tt> function takes two arguments.
The first gives the object to be pushed
and the second specifies the stack on which to push it.<LI>
The <tt>Pop</tt> function takes a single integer argument
which specifies the stack to pop.
</UL>
Choose one of the following implementation approaches:
<OL><LI>
Keep all the stack elements in a single array.<LI>
Use an array of <tt>Stack</tt> objects.<LI>
Use a linked list of <tt>Stack</tt> objects.
</OL><LI>
Design and implement a class called
<tt>DequeAsDoublyLinkedList</tt> that provides
a deque implemented as a doubly-linked list.
Select one of the approaches shown in Figure <A HREF="page163.html#figdeque2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page163.html#figdeque2"><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>.<LI>
In Section <A HREF="page158.html#secstacksdeques" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page158.html#secstacksdeques"><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>,
the <tt>Deque</tt> class is derived from the <tt>Queue</tt> class.
This is the design paradigm known as <em>generalization</em>.
The alternative paradigm is <em>specialization</em>
in which the <tt>Queue</tt> class is derived from the <tt>Deque</tt> class.
Redesign the <tt>Deque</tt> and <tt>Queue</tt> components of the
class hierarchy using specialization.
<P>
<P><A NAME="9243"> </A><A NAME="figexpression"> </A> <IMG WIDTH=575 HEIGHT=121 ALIGN=BOTTOM ALT="figure9062" SRC="img782.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img782.gif" ><BR>
<STRONG>Figure:</STRONG> Expression Tree for <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61602" SRC="img781.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img781.gif" ><BR>
<P><LI>
Devise an approach for evaluating an arithmetic expression
using a <em>queue</em> (rather than a stack).
<b>Hint</b>:
Transform the expression into a tree as shown in Figure <A HREF="page165.html#figexpression" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page165.html#figexpression"><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>
and then do a <em>breadth-first traversal</em> of the tree
<em>in reverse</em> (see Exercise <A HREF="page164.html#exercisestacksreverse2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page164.html#exercisestacksreverse2"><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>).
E.g., the expression <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61602" SRC="img781.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img781.gif" > becomes
<IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61606" SRC="img783.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img783.gif" >.
Evaluate the resulting sequence from left to right using a queue
in the same way that a postfix expression is evaluated using a stack.
<P>
</OL>
<P>
<HR><A NAME="tex2html3939" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html3937" HREF="page130.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page130.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="tex2html3933" HREF="page164.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page164.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="tex2html3941" 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="tex2html3942" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -