Assignment #3 This assignment consists of writing, documenting, and submitting three separate, related programs. Instructions for how to name the files, package them, and submit are at the end. As...

Assignment #3

This assignment consists of writing, documenting, and submitting three separate, related programs. Instructions for how to name the files, package them, and submit are at the end.

As mentioned in class, any output of any program that begins with a pound sign (#) will be ignored. This way you can add debugging information or comments outside of the formatting requirements. You should remove these before you submit but, in a pinch, just be aware we will recognize if it accidentally shows up in your submission.)

The Canvas Wiki Page referenced in the rubric below can be foundhere (Coding Cannon). Canvas doesn't let us embedded links in the Rubric.

Program 3A: Stack

Description

Use the basic linked list Node and List from the previous assignment to create a new class,

class Stack : public List {   ...  } ;

The Stack class will extend list, add the push(string) and pop():string operations. Plus it will add a new, overloaded

push() -- adds an element (the label string) to the top of the stack

pop() -- removes an element from the top of the stack (and returns the label string)

operator

[top] _________    3    2    1 [bot] TTTTTTTTT

Requirements
: For this program, you are two read tokens (words) from the standard input and then, depending on the word, either push the word on the stack or perform and operation (either add, print, or dump). The add operation pops two words off the stack, interprets the words as integers, adds them together and pushes the sum back on the stack (as a string). The print operation pops one element off the stack and displays it. The dump operations is for debugging: it shows the entire stack without changing it at all.

Sample Input and Output:

Test 1 (three inputs):

3
4
-1
add
dump
add
print ^D

3
4
-1
add
dump
[top] _________
3
3
[bot] TTTTTTTTT
add
print
6
dump
[top] _________
[bot] TTTTTTTTT

Test 2 (no inputs): Input is just ^D and the output is nothing

Test 3: Using a pipe on the command line, you can try this:

> echo 1 2 -3 add add print | ./a.out 0
> echo 2 2 2 add 2 add add print | ./a.out
8

You can make up many tests that combine add and print; you can use dump debug.

Program 3B: Queue

Description

Use the basic linked list Node and List as described in class (and previous) to write a method for List that calculates the average wait time for a customer in a line. The input to the program will be two words (called tokens) per line. The first word is a timestamp that represents "the wall clock time" when a customer either enters the line or the wall clock time when the customer exits. The second token is the action: either "enter" or "exit".

For example, if the input is:

0.0 enter 10.0 exit 20.0 enter 25.0 exit

Then the average wait time is 7.5 because the first customer spent 10.0 in line and the second customer spent 5.0, so the average is (10.0+5.0)/2=7.5. (You can choose any unit of time you like: seconds, microseconds, days ... it is irrelevant to the problem.) Since there is no cutting in line, you can assume the customers will exit line in the same order they enter. So the input

0.0 enter 6.0 enter 10.0 exit 11.0 exit

Also produces an average wait time of 7.5.

Requirements
: In addition to the usual grading rubric, the assignment will be based on its functional correctness and its efficiency. Specifically, the following special conditions must be handled by the program:

• If there are no customers exit the line, then the average is undefined. The program should output, "No customers exited, so there is no wait times to average."


• When some customers have exited the line, then the program can compute an average wait time and it should output the result as, "Avg time spent in line is:" followed by default cout output of a double.


• If some customers exited but there are still some in line, then the previous average is to be calculated and output; however the presence of customers should be noted with an additional line, "However, some people are still in line"


• If the input tries to exit more customers than entered, the program will output the line, "Non existant customer exited the line." and immediately exit with return code of 1.


• If the second column is not strictly either "enter" or "exit" then the program will immediately exit with a return code of 1 and output, "syntax error around '{BADTOKEN}'" where {BADTOKEN} is the word that does not match "enter" or "exit".

There are other error conditions, such as when someone does not enter a a valid number for the timestamp or if the input does not have timestamps in strictly increasing order. The program may assume that these will never happen. I.e. the input will be guaranteed to be conforming.