page167.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 124 行
HTML
124 行
<HTML><HEAD><TITLE>Projects</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="tex2html3120" HREF="page168.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3118" HREF="page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3114" HREF="page166.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3122" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION006500000000000000000">Projects</A></H1><P><OL><LI> Enhance the functionality of the RPN calculator given in Program <A HREF="page146.html#progalgorithmsj"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> in the following ways: <OL><LI> Use double-precision, floating-point arithmetic.<LI> Provide the complete repertoire of basic operators: +, -, <IMG WIDTH=8 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline60753" SRC="img676.gif" >, and <IMG WIDTH=10 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline60923" SRC="img721.gif" >.<LI> Add an exponentiation operator and a unary negation operator.<LI> Add a <em>clear</em> method that empties the operand stack and a <em>print</em> method that prints out the contents of the operand stack. </OL><LI> Modify Program <A HREF="page146.html#progalgorithmsj"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page166.html#exercisestacksreverse"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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#progalgorithmsj"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to use a stack of infix expressions. 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="page167.html#projectstacksconvert"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> so that it immediately evaluates the infix expression. That is, create an <tt>infixCalculator</tt> method in the style of Program <A HREF="page146.html#progalgorithmsj"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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=46 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline60929" SRC="img722.gif" >, i.e., <I>S</I> is the string of length zero,<LI> <IMG WIDTH=75 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60933" SRC="img723.gif" >,<LI> <IMG WIDTH=75 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline60935" SRC="img724.gif" >,<LI> <IMG WIDTH=74 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60937" SRC="img725.gif" >,<LI> <IMG WIDTH=71 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline60939" SRC="img726.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. For example, <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.<LI> Design and implement a <tt>MultipleStack</tt> class which provides <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60945" SRC="img727.gif" > stacks in a single container. The declaration of the class should look something like this:<PRE>class MultipleStack(Container): def __init__(self, numberOfStacks): ... def push(self, obj, whichStack): ... def pop(self, whichStack): ... # ...</PRE> <UL><LI> In addition to <tt>self</tt>, the <tt>__init__</tt> method takes a single integer argument that specifies the number of stacks in the container.<LI> In addition to <tt>self</tt>, the <tt>push</tt> method takes two arguments. The first gives the object to be pushed and the second specifies the stack on which to push it.<LI> In addition to <tt>self</tt>, the <tt>pop</tt> method 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 implements the <tt>Deque</tt> interface using a doubly-linked list. Select one of the approaches shown in Figure <A HREF="page165.html#figdeque2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> In Section <A HREF="page158.html#secstacksdeques"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, the <tt>DequeAsArray</tt> class extends the <tt>QueueAsArray</tt> class. Redesign the <tt>DequeAsArray</tt> and <tt>QueueAsArray</tt> components of the class hierarchy making <tt>DequeAsArray</tt> the base class and deriving <tt>QueueAsArray</tt> from it.<P><P><A NAME="8485"> </A><A NAME="figexpression"> </A> <IMG WIDTH=575 HEIGHT=121 ALIGN=BOTTOM ALT="figure8309" SRC="img729.gif" ><BR><STRONG>Figure:</STRONG> Expression tree for <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60961" SRC="img728.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="page167.html#figexpression"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page166.html#exercisestacksreverse2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). For example, the expression <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60961" SRC="img728.gif" > becomes <IMG WIDTH=81 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline60965" SRC="img730.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="tex2html3120" HREF="page168.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3118" HREF="page130.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3114" HREF="page166.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3122" 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 + -
显示快捷键?