Learning objectives:

• Relationships, Inheritance and Polymorphism in C++

• STL vectors

• Decorator and Observer design patterns

• Questions 1a, 3a, 4a are due on Due Date 1; questions 1b, 2, 3b and 4b are due on Due Date 2.

• On this assignment, you are responsibility for your own testing. For each question (where required) you are given a compiled executable program that is a program representing a solution to each question. You should use these provided executables to help you write your test cases, as they can show you the resultant output for given inputs. 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/UML diagrams for C++ programs that you will later submit by Due Date 2.

Test suites will be in a format compatible with the runSuite script that you used in CS136L and the previous assignments. Note that test suite submission zip files are restricted to contain a maximum of 40 tests. The size of each input ( .in) file is also restricted to 500 bytes. There is also a limit for each output file ( .out), but none of your tests should be able to create such a large output file that you would normally encounter it.

• If we do not explicitly tell you how to handle a particular type of invalid input, then you do not need to worry about that case since it is considered to be undefined behaviour. Such cases (invalid inputs that fall under the umbrella of undefined behaviour) should not be submitted as part of a test suite. This applies to all assignments and questions in the course.

• Due to the unstable nature we have been encountering, for this assignment do not use import; instead use #include (as taught in CS 136 and 136L) to include C++ libraries. The modularization of your programs should also follow the style learned in CS 136. Do not use:

– export  module  name; in your interface file, or

– module  name; in your implementation file.

Instead, create  .h files as your interface files and remember to include your interface file in your  .cc implementation file.

To compile your programs, you will need to create a Makefile and use:

g++20="g++  -std=c++20  -Wall  -Werror=vla  -g"

You may want to add this as a new alias. This should resolve a number of compiler issues we have been encountering.

• 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 . For this assignment, you are not allowed to use the array (i.e., []) forms of new and delete. Marmoset will be setup to reject submissions that use C-style I/O or MM, or libraries other than the ones specified above.

• There will be a hand-marking component in this assignment, whose purpose is to ensure that you are fol- lowing an appropriate standard of documentation and style, and to verify any assignment requirements not directly checked by Marmoset. Please code to a standard that you would expect from someone else if you had to maintain their code.  We will not answer Piazza questions about coding style; use your best judgment. Further comments on coding guidelines can be found here: https://www.student.cs. uwaterloo.ca/ ˜cs246/S23/codingguidelines.shtml

• We have provided some code and sample executables under the appropriate a3 subdirectories. These exe- cutables have been compiled in the CS student environment and will not run anywhere else.

• Before asking on Piazza, see if your question can be answered by the sample executables we provide. You are not permitted to ask any public questions on Piazza about what the programs that make up the assignment are supposed to do.  Questions found in violation of this rule will be marked private or deleted; repeat offences could be subject to discipline.

Question 1

(50% of DD1; 20% of DD2)  In this problem, you will write a program to read and evaluate arithmetic expressions. There are four kinds of expressions:

• lone integers

• variables, which have a name (letters only, case-sensitive, but cannot be the words done, ABS, or NEG)

• a unary operation (NEG or ABS, denoting negation and absolute value) applied to an expression

• a binary operation (+, -, *, or /) applied to two expressions

Expressions will be entered in reverse Polish notation (RPN), also known as postfix notation, in which the operator is written after its operands. The word done will indicate the end of the expression. For example, the input

12  34  7  +  *  NEG  done

denotes the expression −(12 ∗ (34 + 7)).  Your program must read in an expression, print its value in conventional infix notation, and then initiate a command loop, recognizing the following commands:

•  set  var  num sets the variable var to value num. The information about which variables have which values should be stored as part of the expression object, and not in a separate data structure (otherwise it would be difficult to write a program that manipulates more than one expression object, where variables have different values in different expres- sions).

• unset  var reverts the variable var to the unassigned state.

• print prettyprints the expression. Details in the example below.

• eval evaluates the expression. This is only possible if all variables in the expression have values (even if the expression is x  x  -, which is known to be 0, the expression cannot be evaluated). If the expression cannot be evaluated, you must raise an exception and handle it in your main program, such that an error message is printed and the command loop resumes. Your error message must print the name of the variable that does not have a value (if more than one variable

lacks a value, print one of them).

For example (output in italics):

1  2  +  3  x  -  *  ABS  NEG  done

- | ((1  +  2)   *   (3  -  x)) |

eval

set  x 4

print

- | ((1  +  2)   *   (3  -  4)) |

- 3

set  x 3

print

- | ((1  +  2)   *   (3  -  3)) |

eval

0

unset  x

print

- | ((1  +  2)   *   (3  -  x)) |

eval

x  has  no  value .

Numeric input shall be integers only. If any invalid input is supplied to the program, its behaviour is undefined.

Note that a single run of this program manipulates one expression only. If you want to use a different expression, you need to restart the program.

To solve this question, you will define a base class Expression, and a derived class for each of the the four kinds of ex- pressions, as outlined above. Your base class should provide virtual methods prettyprint, set, unset, and evaluate that carry out the required tasks.

To read an expression in RPN, you will need a stack. Use cin with operator >> to read the input one word at a time. If the word is a number, or a variable, create a corresponding expression object, and push a pointer to the object onto the stack. If the word is an operator, pop one or two items from the stack (according to whether the operator is unary or binary), convert to the corresponding object and push back onto the stack. When done is read, the stack will contain a pointer to a single object that encapsulates the entire expression.

Once you have read in the expression, print it out in infix notation with full parenthesization, as illustrated above. Then

accept commands until EOF.

Note: Your program should be well-documented and employ proper programming style. It should not leak memory. Markers will be checking for these things.

Note: The design that we are imposing on you for this question is an example of the Interpreter pattern (this is just FYI; you don’t need to look it up, and doing so will not necessarily help you).

a) Due on Due Date 1: A UML diagram (in PDF format q1UML .pdf) for this program. There are links to UML tools on the course website.  Do not handwrite your diagram.  Your UML diagram will be graded on the basis of being well-formed, and on the degree to which it reflects a correct design.

b) Due on Due Date 2: Implement this program in C++. You must include a Makefile, such that issuing the command make will build your program. The executable should be called a3q1. Submit all the files that make up your program (along with any additional source files, if you created any) in your zip file, a3q1b . zip.

Question 2

(0% of DD1; 20% of DD2) This problem continues Problem 1. Suppose you wish to be able to copy an expression object. The problem is that if all you have is an Expression pointer, you don’t know what kind of object you actually have, much less what types of objects its fields may be pointing at. Devise a way, given an Expression pointer, to produce an exact (deep) copy of the object it points at. Do not use any C++ language features that have not been taught in class.

When you have figured out how to do it, implement it as part of your solution for Problem 1, and add a copy command to your interpreter. If the command is copy, you will execute the following code:

Expression  *theCopy  =   (   . . .  create  a  copy  of  your  main  Expression  object   . . . ) cout  << theCopy->prettyprint()  << endl;

theCopy->set("x",  1);

cout  << theCopy->prettyprint()  << endl;;

cout  << theCopy->evaluate()  << endl;

delete  theCopy;

The copy will contain the same variable assignments as the original expression. However, setting the variable x to 1 in the copy should not affect the value of x in the original expression. x may or may not be the only unset variable in the expression.

If there are other unset variables, then naturally, an exception will be raised, and you should handle it in the same way as previously.

This problem will be at least partially hand-marked for correctness. A test suite is not required. Note that Marmoset will provide only basic correctness tests of output. If it is found during handmarking that you did not complete this problem according to our instructions, you correctness marks from Marmoset will be revoked.

Due on Due Date 2: Implement this program in C++. You must include a Makefile, such that issuing the command make will build your program. The executable should be called a3q2. Submit all the files that make up your program (along with any additional source files, if you created any) in your zip file, a3q2 . zip. Your Q1 UML should not include your solution for Q2.

Question 3

(50% of DD1; 30% of DD2)

In this question you will be building a fun ASCII art drawing and animation program! You’ll start with a blank canvas, and will draw rectangles consisting of characters of your choosing on that canvas (remember that any point is a 1x1 rectangle, so you can draw anything!), and choose how your drawing will evolve with time.

The key to the functioning of this program is the Decorator pattern. A blank canvas will respond with a blank space to any query about the contents of a cell at a particular row or column. However, it can be decorated by rectangles, which will respond in their own way to the same query, or will pass it along to the ASCII art element behind them. Moreover, the key to the animation aspect of this program is that the response to a query for a cell can be time-varying. So a query to a cell actually involves three parameters: the row, the column, and the tick count (where the latter is the number of rendering events that have occurred since the last time the animation was reset).

You are to support the following kinds of ASCII art elements:

• filled box: A simple solid rectangle, specified by top and bottom row (inclusive) and left and right column (inclusive). Does not move.

• blinking box: A box that is displayed when the tick count is even, and is transparent otherwise.

• moving box: A box that moves one position (either up, down, left, or right) with each tick.

• mask box: A box that is invisible unless there is a visible art element beneath it. In that case, the part of the mask that lies above the art below becomes visible and covers that art. Does not move.

The provided starter code comes with a test harness that supports the following commands:

•  render — causes the current artwork to be displayed, with a frame around it, so that the boundaries are clear (see the provided executable for details). Counts as a tick.

•  animate  n — renders the artwork n times.

•  reset — resets the tick count to 0.

•  filledbox  t  b  l  r  c — adds a filled box with given top, bottom, left, right boundaries, filled with the character c (assumed to be non-whitespace and printable ASCII in the range 0– 127). Invalid if top exceeds bottom or left exceeds right.

• blinkingbox  t  b  l  r  c — adds a blinking box, with parameters understood as above.

• movingbox  t  b  l  r  c  dir — adds a moving box, with first five parameters understood as above and a direction dir, which can be one of u  d  l  r.  Clarification: These parameters are understood to be the position of the box when the tick count is 0. If the tick count is not 0 when the moving box is placed, it will show up shifted by a number

of positions equal to the current tick count.

• maskbox  t  b  l  r  c — adds a mask, with parameters understood as above.

Note: Some implementation notes for this problem can be found in the provided README .txt.  Be sure to read and follow it!

Important: As the point of this problem is to use the Decorator pattern, if your solution is found in handmarking to not employ the Decorator pattern, your correctness marks from Marmoset will be revoked.

Note:  Your program should be well-documented and employ proper programming style.  It should not leak memory. Markers will be checking for these things.

Due on Due Date 1: Submit your test suite (suiteq3 .txt and all necessary files) in the file a4q3a . zip.

Due on Due Date 2: Implement this program in C++. You must include a Makefile, such that issuing the command make will build your program. The executable should be called a3q3. Submit all the files that make up your program (along with any additional source files, if you created any) in your zip file, a3q3b . zip.

Question 4

(0% of DD1; 30% of DD2) Note:  This problem asks you to work with XWindows graphics.  Well before starting this question, make sure you are able to use graphical applications from your student.cs session. If you are using Linux you should be fine (if making an ssh connection to a campus machine, be sure to pass the -Y option). If you are using Windows and putty, you should download and run an X server such as XMing, and be sure that putty is configured to forward X connections. If you are using a Mac, download and run XQuartz, and pass the -Y option when making ssh connections. Alert course staff immediately if you are unable to set up your X connection (e.g. if you can’t run xeyes).

Also (if working on your own machine) make sure you have the necessary libraries to compile graphics. Try executing the following:

g++20  window .cc  graphicsdemo .cc  -o  graphicsdemo  -lX11

Be sure to add the -lX11 option to the linking line of your Makefile (that’s lowercase-L, X, eleven, and it goes at the end of the linking line in your Makefile).

This question extends the previous question, in which you wrote an ASCII art animator program. In that problem, you had a studio object that managed the tick count, and was responsible for rendering your artwork to an output stream (std::cout). In this problem, we’ll take that second responsibility away from the Studio class by employing the Observer pattern. Your Studio class will become a concrete“subject”class in this new model.

If you wish to actually see your artwork, you will need to create an observer object and attach it to the subject. But why stop at one? You could, in fact, create several observers! (And why should they all be necessarily text-based? More on that in a bit.) A bunch of observers all observing and rendering the same text is boring. But who says they all have to be watching the same part of your artwork? And who says your artwork has to be limited to just a 10x10 grid?

No, in this problem, your art has rows and columns spanning the entire range of 32-bit integers!  But each of your observers, of course, will only see a much smaller portion of it.

In this problem, you will restructure your solution so that, in addition to following the Decorator pattern, it also conforms to the Observer pattern. As well, incorporate the other changes described above.

The test harness for this problem includes all of the commands from the previous problem. Those whose meanings have changed are described below, along with the new commands specific to this problem:

•  render — causes all observers to render their images. Images should be displayed in the order the observers were registered with the subject.

•  addtext  t  b  l  r — adds a text-based observer watching a portion of the image with the given top, bottom, left, right boundaries. Invalid if top exceeds bottom or left exceeds right. This observer, when notified, will display its view to std::cout.

•  addgraphics  t  b  l  r — adds a graphical observer, with parameters understood as above.

For the graphical observers, you will use the Xwindow class that has been provided to you.  Make sure you have a working XWindows server running on your computer, such that you can run graphical applications over an SSH connection. Test this EARLY. Your windows will be of size 10T by 10c, where T is the number of rows being observed, and c is the number of columns being observed. Represent the rendered objects by colour-coded 10x10 squares: