首页 > > 详细

EIE111辅导、C++程序设计调试、讲解c/c++语言、辅导data 讲解Database|讲解留学生Prolog

Homework 3 : C++ class inheritance
CIS111&EIE111 2020Spring
1. Overview
We will use the knowledge of C++ classes properly as much as possible (chapter 10 to 15), for the
purpose of reusing code.
2. Tasks of the homework
2.1 Implement the ADT of Stack and Queue using
classes.
The abstract data types (ADT) of Stack and Queue are described in the textbook and in the classes.
We will implement stack and queue using classes, with the following requirements.
The stack should be implemented in two different ways:
by a linked list
by an array (can be C++ array or vector class)
The queue should be implemented in two different ways:
by a linked list
by an array. It could be a circular array (Chapter 17 of C Primer plus), or C++ array or vector
class.
Use classes extensively.
Linked list should be a class.
If circular array is implemented, it should be a class.
Each implementation of a stack or queue should be a different class.
Design other needed classes.
Use inheritance relationships between classes extensively. A possible design could be like the
following:
An abstract base class (ABC) Container, which is the base class of the two classes Stack and
Queue.
Stack is an ABC that is the base class of two concrete classes: Stack_of_linked_list,
Stack_of_array
Queue is an ABC that is the base class of two concrete classes: Queue_of_linked_list,
Queue_of_array
Design and implement each class properly. Especially take care of the special members including:
Constructors, including default constructor, copy constructor.
The destructor.
Overloaded operators if they are useful. Usually the = and [] operators are useful if they are
overloaded.
The friend functions. Usually the << and >> operators should be overloaded by friend
functions.
2.2 Parsing an expression into a queue of tokens.
Given an expression, a sequence of tokens should be parsed and recorded in a queue. It is same as
in homework 2, but the tokens are saved in a queue.
2.3 Implementing the algorithm of evaluating infix expressions.
The stack based algorithm is the same one as homework 1 and 2, but now the code are organized
using classes
2.4 IMplementing the algorithm of evaluating postfix
expressions.
Post expressions is also called Reverse Polish Notation (RPN), which has the advantage of the ease
of evaluation without the need of parenthesis.
For example, the infix expression
(2 + 10) / (9 - 6)
can be translated into a postfix expression:
2 10 + 9 6 - /
There is a simple algorithm to evaluate using one stack, which is described in [6] [7] [8], and its
pseudo-code (from [7]) is described below with some minor adjustment.
// pseudo code of evaluating a postfix expression
Initialize(Stack S)
x = ReadToken(); // Read Token from a queue
while(x)
{
if ( x is Operand )
Push ( x ) Onto Stack S.
if ( x is Operator )
{
Operand2 = Pop(Stack S);
Operand2 = Pop(Stack S);
value = Evaluate (Operand1,Operand2,Operator x);
Push (value) onto Stack S.
}
x = ReadNextToken(); // Read Token
}
// The value of the expression is saved on the top of the stack
answer = Pop(Stack S);
An example of the process of evaluating a postfix expression is described below [7].
2.4 Translate an infix expression into a postfix expression.
The Shunting-yard algorithm [5] can translate the an infix expression into a postfix expression. The
input is a sequence of tokens of the infix expression saved on a queue, and the output is the sequence
of tokens of the postfix expression saved in another queue. The computation of the algorithm uses a
stack.
Some Pseudo-code of the algorithm is described in [5] and [8] whose documents are available as offline
files of this homework.
When you implement this algorithm, you should use two different Queue classes for the input and
output, to test the different implementation of Queue.
2.5 Test your functions with user interaction.
The interaction part of the program can be designed as follows:
Repeat:
Show a menu that has (at least) the following choices:
a) Asks for an infix expression, and print its tokens
b) Asks for an infix expression, and print its value
c) Asks for a postfix expression, and print its value
d) Asks for an infix expression, translate it into a postfix expression and print it.
q) Quit the loop.
Let the user make a choice and executes its operation accordingly.
2.6 Other requirements and suggestion
Same as homework 2, use C++ code style, do not use C and C library, when possible.
Testing the two different Stack classes (the two stacks needed for infix expression evaluation),
and the two different Queue classes (the input and output of translating infix expression to postfix
expression)
The knowledge of classes from chapter 10 to 13 will be sufficient. If you uses knowledge of
chapter 14 and 15 properly, you can obtain some bonus points.
Implement and test tasks 2.1 2.2 and 2.3 first. Do tasks 2.4 and 2.5 later.
Different tasks will be graded differently. Task 2.1 is the most important part.
3. Homework Submission
Submit your homework at moodle.must.edu.mo
At most 3 students can form a group to do and submit the homework together. You can also do
the homework alone.
Only one student in the group need to submit the homework.
Only text files of source code and records can be submitted ( .cpp .h, .txt ).
Provide a file readme.txt (other formats are ok, like .md, .pdf, .doc, .docx ) that describe the
following details
The names of the group members.
How did your group members work together. Say something about your cooperation
experience. How did make progresses in doing this homework.
The status of your program. What has been achieved. what are missing or lacking.
A list of the C++ features (chapter 1 to 15) that are used in your homework, where and how it
is used in your homework. Especially, describe the class inheritance features that are used in
your program, the special features that deserve good grades and bonus points.
How to compile and run your program. Record some screen outputs (copy and paste the
command history).
The extra feature (if there is any) of your work.
Deadline : June 10 2020 (Wednesday), 10pm.
References
[1]
http://csis.pace.edu/~murthy/ProgrammingProblems/16_Evaluation_of_infix_expressions
[2]
http://homepage.divms.uiowa.edu/~ghosh/2116.61.pdf
[3] C++ Primer Plus, 6th Edition https://www.pearson.com/us/higher-education/program/Prata-CPrimer-Plus-6th-Edition/PGM18461.html
[4] Reverse Polish notation https://en.wikipedia.org/wiki/Reverse_Polish_notation
[5] Shunting-yard algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm
[6] Algorithm for Evaluation of Postfix Expression https://www.thecrazyprogrammer.com/2014/02/cprogram-and-algorithm-for-evaluation-of-a-postfix-expression.html
[7] Algorithm for Evaluation of Postfix Expression http://www.c4learn.com/data-structure/algorithmevaluation-of-postfix-expression/
[8] Postfix algorithms http://personal.denison.edu/~havill/algorithmics/algs/postfix.pdf

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!