CS246留学生编程代做、C++语言程序调试、C++编程代做

日期：2020-10-24 10:35

ASSIGNMENT #3: C++ CLASSES CS246, FALL 2020

Assignment #3: C++ Classes

Due Date 1: Wednesday, October 28, 2020, 5:00 pm

Due Date 2: Wednesday, November 04, 2020, 5:00 pm

Online Quiz: Wednesday, November 11, 2020, 5:00 pm

Topics that must have been completed before starting Due Date 1:

1. Software Testing, produceOutputs and runSuite from A1

Topics that must have been completed before starting Due Date 2:

1. Object-Oriented Programming: Introduction

2. Object-Oriented Programming: Special class members

3. Object-Oriented Programming: Advanced object uses

4. Object-Oriented Programming: Invariants and Encapsulation

5. Design Patterns: Iterator

Learning objectives:

? Object-Oriented programming, Invariants and Encapsulation, Iterator design pattern

? C++ classes, constructors, destructors, and operations

? Dynamic memory allocation for C++ objects and arrays

? Questions 1a and 2a are due on Due Date 1; the remaining questions are due on Due Date 2. You must

submit the online quiz on Learn by the Quiz date.

? On this and subsequent assignments, you will take responsibility for your own testing. This assignment is

designed to get you into the habit of thinking about testing before you start writing your program. If you

look at the deliverables and their due dates, you will notice that there is no C++ code due on Due Date 1.

Instead, you will be asked to submit test suites for C++ programs that you will later submit by Due Date 2.

Test suites will be in a format compatible with that of the latter questions of Assignment 1, so if you did a

good job writing your runSuite script, that experience will serve you well here.

? Design your test suites with care; they are your primary tool for verifying the correctness of your code. Note

that test suite submission zip files are restricted to contain a maximum of 40 tests. The size of each input

(.in|.args) file is also restricted to 300 bytes, and each output file (.out) is restricted to 1,000 bytes.

This is to encourage you not combine all of your testing eggs in one basket.

? You must use the standard C++ I/O streaming and memory management (MM) facilities on this assignment;

you may not use C-style I/O or MM. More concretely, you may #include the following C++ libraries

(and no others!) for the current assignment: iostream, fstream, sstream, iomanip, string, and

utility. Marmoset will be setup to reject submissions that use C-style I/O or MM, or libraries other than

the ones specified above. Note that this means you cannot use vector or other data structures that require

an additional library to be imported.

? We will manually check that you follow a reasonable standard of documentation and style, and to verify

any assignment requirements that are not automatically enforced by Marmoset. Code to a standard

that you would expect from someone else if you had to maintain their code. Further comments on coding

guidelines can be found here: https://www.student.cs.uwaterloo.ca/?cs246/F20/

codingguidelines.shtml

Page 1 of 7

ASSIGNMENT #3: C++ CLASSES CS246, FALL 2020

? We have provided some code and sample executables in the subdirectory codeForStudents under the

appropriate subdirectories. These executables have been compiled in the CS student environment and

will not run anywhere else.

? You may not ask public questions on Piazza about what the programs that make up the assignment

are supposed to do. A major part of this assignment involves designing test cases, and questions that ask

what the programs should do in one case or another will give away potential test cases to the rest of the

class. Questions found in violation of this rule will be marked private or deleted; repeat offences could be

subject to discipline.

Coding Questions

Questions 1, 2, and 3 are part of the coding assessment and may be publicly discussed on Piazza so long as solutions are

neither discussed nor revealed.

Question 1

(40% of DD1; 32% of DD2) In this exercise, you will write a C++ class to control a simple robotic drone exploring some

terrain. Your drone starts at coordinates (0,0), facing North.

Some starter code has been provided for you in the folder a3/codeForStudents/drone, along with a sample executable.

You may not change the contents of drone.h and position.h other than by adding private instance

members and comments, i.e., the public interface must stay exactly the same.

Use the class Position declared in position.h for the coordinates.

class Position {

int ew, ns;

// public methods; see position.h for details

};

The east-west direction is the first component of a position (east is positive, west is negative). The north-south direction is

the second (north is positive, south is negative).

The operator<< for a Position must also be implemented, which should print the current values of the position in

the format: (ew,ns) (no spaces or line breaks). Please ensure that your output matches that of the sample executable.

Use the class Drone declared in drone.h to implement the drone’s functionality.

class Drone {

Position cur; // current position

int dir; // 0 = N, 1 = E, 2 = S, 3 = W

int numSteps; // total number of steps walked by the drone

// public methods; see drone.h for details

};

The operator<< for a Drone must also be implemented, which should print the current status of the drone as:

Current Position: (ew,ns), Facing <direction>, where <direction> is North, East, South, or

West (no line breaks). Please ensure that your output matches that of the sample executable.

You must create the files position.cc and drone.cc and implement all the operations specified in position.h

and drone.h.

The test harness main.cc is provided with which you may interact with your drone for testing purposes. The test

harness is not robust and you are not to devise tests for it, just for the Drone class. Do not change this file.

The test harness supports the following commands:

Page 2 of 7

ASSIGNMENT #3: C++ CLASSES CS246, FALL 2020

Command Description

f n Moves forward by n steps in the current direction. n must be positive.

b n Moves backward by n steps in the current direction. n must be positive.

l Turns 90 degrees to the left.

r Turns 90 degrees to the right.

c Prints the current status of the drone.

t Prints the total number of steps walked by the drone.

m Prints the Manhattan distance of the current position to the origin.

Notes:

? The total number of steps walked by the drone is a simple sum of all the forward and backward steps. For example, if

the drone walks 5 steps forward, 2 backward, turns right, and walks 5 steps forward, the total number of steps is just

5 + 2 + 5 = 12.

? The Manhattan distance is calculated as the absolute north-south displacement plus the absolute east-west displacement.

For example, the Manhattan distance of the position (3,4) to the origin is 7 (i.e., 3 + 4). The Manhattan distance of

the position (-3,4) to the origin is also 7. See diagram below.

Submission:

(a) Due on Due Date 1: Design the test suite suiteq1.txt for this program and zip the suite into a3q1a.zip.

(b) Due on Due Date 2: Implement this in C++ and place the files drone.h, drone.cc, position.h, and position.cc

in the zip file, a3q1b.zip. We will provide the Makefile and main.cc to test your submission.

Page 3 of 7

ASSIGNMENT #3: C++ CLASSES CS246, FALL 2020

Question 2

(60% of DD1; 60% of DD2) A markup language is a system for annotating documents. In markup languages such as HTML

and XML, annotations consist of tags, identified by the starting and end characters < >. Tags can further contain attributes

or children tags/text and are closed by </ >. For example, in the following excerpt, document, body, and text are tags.

The text tag contains a id attribute, currently set to "t1", and a value attribute, currently set to "Hello CS 246".

<document>

<body>

<text id="t1" value="Hello CS 246">

</text>

</body>

</document>

In this exercise, you will write a class to manage tags in a document. Our markup language is loosely inspired by HTML

and XML, but it is quite simplified. Our tags can be of any type (such as document, body, or text) and can optionally

contain the attributes id and value (and no other). Additionally, they can contain any number of children tags. There is

always a top-level document tag. The example document above is a valid document in our markup language and also an

example of the formatting that should be used by the program when printing the tags.

We have provided the declaration of the Tag class in the file tag.h. You may not change the contents of tag.h other

than by adding private instance members and comments, i.e., the public interface must stay exactly the same.

class Tag {

std::string type; // the type of the tag

std::string id; // the id attribute of the tag

std::string value; // the value attribute of the tag

Tag *parent; // pointer to the parent tag

Tag **children; // array of children tag pointers

int childrenLength; // current number of children tags

int childrenCapacity; // current capacity of the children array

// public methods; please check tag.h for details

};

Your job is to implement all the methods of the Tag and TagIterator classes in the file tag.cc. Please read carefully

the documentation for each method in tag.h. The comments explain what they must do.

Implementation details:

? The children array contains the children Tags. When a Tag is created, initialize children to nullptr. Initialize

childrenLength and childrenCapacity to zero. When the first child Tag is added, create an array in the heap

with size one. You must keep track of the current capacity (size) of the array in childrenCapacity and the current

number of children tags (positions used in the array) in childrenLength. You will increase the capacity of the array

using a doubling strategy. Each time a new child Tag is added, if the length of the array is already equal to the capacity,

you must double the current capacity of the array (i.e., create a new array with double the capacity of the current one

and move all the children Tags over to the new array). When children tags are removed from the array, you do not need

to reduce the capacity.

? Because we test your submission by comparing the output of your program with the expected output of the correct

program, you will lose marks if your Tag::print() does not precisely match the output of our implementation.

You can use the document at the top of the page as an example of how the formatted output should look like. Note

that each tag start markup and tag end markup should be printed on a new line. Children tags must be indented with

two spaces per level. We are also providing you a sample executable that produces the correct output. Please test

the provided executable for every potential type of output and ensure that your solutions matches the sample output

precisely (use an utility like diff to ensure that the outputs are identical; don’t rely only on a visual inspection). The

produceOutputs and runSuite scripts that you wrote as part of A1 can help you do that.

Page 4 of 7

ASSIGNMENT #3: C++ CLASSES CS246, FALL 2020

? We also provided the declaration of TagIterator, which is a implementation of the Iterator design pattern

for the children array. You must also implement the methods of this class. Used together with the methods

Tag::begin() and Tag::end(), it can be used by a client to iterate through all the children of a tag.

? You can implement the operator<< for Tags (also declared in tag.h) by just calling the tag’s print method.

? Your program must not leak any memory.

A test harness is provided in main.cc (which uses controller.[h|cc]). You can use it to test your Tag class. The

test harness is not robust and you are not to devise tests for it, just for the Tag class. Do not change these files. We have

also provided a sample executable (markup) that you can use for tests.

The test harness supports the following commands. Please read the contents of main.cc and controller.[h|cc]

if you need more details about them. Note that the harness keeps track of the “current” tag at any moment and most of the

commands operate on it. Also, note that the harness automatically creates a top-level document tag. You can set its attributes

and add children to it. However, you cannot delete, copy, or move the document tag.

Command Description

print Prints the current tag to the standard output.

add type Creates a new tag of the type specified by the argument, adds it as a child of the current tag, and

makes it the new current tag. Note that type cannot be "document".

delete Deletes the current tag, removes it from its parent, and makes its parent the new current tag.

parent Sets the parent of the current tag as the new current tag.

up Sets the topmost tag (<document>) as the current tag.

id val Sets the id attribute of the current tag to val. Note that val cannot contain whitespaces.

value val Sets the value attribute of the current tag to val. Note that val cannot contain whitespaces.

find type Finds the first tag that is a child of the current tag and has the specified type. If such a tag if found,

it is set as the current tag. Otherwise, nothing happens.

list Lists all the children of the current tag.

cut Copies the current tag to the program’s internal clipboard and marks it as cut.

copy Copies the current tag to the program’s internal clipboard.

paste Replaces the contents of the current tag with the contents of the tag currently in the clipboard.

The tag in the clipboard is moved or copied depending on whether it was originally cut or copied.

Note that you cannot cut and paste a tag into itself or a child of itself (but you can copy it).

pasteChild Adds a new child to the current tag, whose contents comes from the tag currently in the clipboard.

The tag in the clipboard is moved or copied depending on whether it was originally cut or copied.

Note that you cannot cut and paste a tag into itself or a child of itself (but you can copy it).

quit Terminates the program.

Submission:

(a) Due on Due Date 1: Design the test suite suiteq2.txt for this program and zip the suite into a3q2a.zip.

(b) Due on Due Date 2: Implement this in C++ and place the files tag.h and tag.cc in the zip file, a3q2b.zip. We

will provide the Makefile, main.cc, and controller.[h|cc] to test your submission.

Page 5 of 7

ASSIGNMENT #3: C++ CLASSES CS246, FALL 2020

Question 3

*** BONUS *** This question is worth 5% as a bonus, i.e., if the assignment is out of 100 marks, and you obtain full marks

in this question, your maximum assignment grade is 105 marks.

In this question, you will extend your solution from Question 2 to support these two additional commands:

Command Description

next

? If the current tag is not the last child tag in its parent, then set the next sibling (i.e., the tag

that comes right after the current one in its parent’s children array) as the current tag in the

controller and call Controller::printCurrent() to print the current status

to cout.

? If the current tag is already the last child tag in its parent, just print "Current tag is

already the last child of its parent." to cerr and do nothing else.

? If the current tag is the top-level tag (i.e., it does not have a parent), just print "Current

tag is the upper level tag." to cerr and do nothing else.

previous

? If the current tag is not the first child tag in its parent, then set the previous sibling (i.e., the

tag that comes right before the current one in its parent’s children array) as the current tag

in the controller and call Controller::printCurrent() to print the current

status to cout.

? If the current tag is already the first child tag in its parent, just print "Current tag is

already the first child of its parent." to cerr and do nothing else.

? If the current tag is the top-level tag (i.e., it does not have a parent), just print "Current

tag is the upper level tag." to cerr and do nothing else.

Because this is a bonus question, you are not given any starting code for it. Therefore, you should use your solution from

Question 2 as the starting code. For this question, you are allowed to modify any file in the solution. But please note that your

modifications must follow the C++ and object-oriented programming guidelines taught in this course.

You will need to modify the main() function to support the two additional commands and make any other changes

necessary to the program to make them work. You must ensure that the other commands of the test harness continue working

as before, i.e., the only change in the program’s behaviour is that two new commands are now supported. Your updated

solution must also not leak any memory.

We have provided a sample executable (markup bonus) that you can use for tests.

Submission:

(a) Due on Due Date 1: Nothing.

(b) Due on Due Date 2: Implement this in C++ and place all the files necessary to compile your program (including the

Makefile) in a3q3b.zip. Your Makefile must create an executable named markup. Note that the executable name

is case-sensitive.

Page 6 of 7

ASSIGNMENT #3: C++ CLASSES CS246, FALL 2020

Written Assessment

Questions 4, 5, and 6 are part of the written assessment, and may not be publicly discussed on Piazza (or anywhere else).

Question 4

(2% of DD2)

(a) Explain in your own words what a class and an object are with respect to object-oriented programming (not C++

specific).

(b) Provide a code snippet in C++ that includes a class and an object and label each with a comment.

Question 5

(2% of DD2) Consider the following program. If there are any errors, identify them (in what line they occur and what is the

problem). Otherwise, just state “No error”.

struct Point {

int x, y;

Point(int x, int y) : x{x}, y{y} {}

};

int main() {

Point p1[3];

Point p2[3] = {Point{1,1}, Point{2,2}, Point{3,3}};

Point *p3 = new Point[3];

Point &p4 = {Point{1,1}, Point{2,2}, Point{3,3}};

}

Question 6

(4% of DD2) Consider the following Pixel class that should enforce the class invariant that the values for the data fields r,

g, and b must be in the range 0 to 255.

struct Pixel {

unsigned int r; // value for red

unsigned int g; // value for green

unsigned int b; // value for blue

};

Explain how you would change the definition, without changing the types of the fields, so that the invariant is enforced.

Page 7 of 7