#
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