CMPT 225 Assignment 2 (5%)

Marking Criteria:

For all problems, your solutions will be judged by how appropriately you solved the problem. That

includes not just the correctness and efficiency of your code, but also how your code is presented,

i.e., coding style. The best code contains class invariants, assertions, preconditions, postconditions,

and descriptions of your algorithms, written in a high-level voice.

Follow the instructions carefully. Changing header files is particularly hazardous because your code

may not build when we try to test it. Code that doesn’t build never receives a mark much higher

than 0.

0. [0 marks] Care Package Download

Download the care package from the course web page and unzip it. It contains your base

code.

1. [30 marks] Linked-List Stack

The overall goal of this question is to implement a Stack ADT using a linked-list data structure

which pushes the topmost element to the tail of the list. This will be different than the in-class

implementation where the elements were pushed to the head of the list.

We’re not suggesting this is a particularly good choice of data structure, that is it will force

at least one of the operations to have a O(n) number of steps. The point of the exercise is to

give you an opportunity to program an ADT with a linked list.

What You Need to Write

You are going to complete the implementation of a Stack ADT with a specific data structure.

That data structure is a singly linked list in which pushed items are placed at the tail of the

linked list. (Similarly, popped items will be removed from the tail of the list.)

Students who submit a linked list implementation where the top of the stack was at the head

of the list will receive 0 for this question.

Complete your implementation in Stack.h and Stack.cpp, and then submit them to CourSys.

2. [10 marks] Running-Time Analysis

Referring to the proposed implementation in Question 1, analyze the total running time

required to push n items to the Stack. Next, analyze the total running time required to pop

those n items from the Stack. A detailed analysis is expected, i.e., if you present a final

answer only, you will be unhappy with your grade.

Type your analysis in Analysis.txt and submit to CourSys.

3. [30 marks] Evaluating Infix Expressions

Though a stack can be employed to calculate expressions in postfix notation, the reality is

most humans don’t write expressions that way: we tend to use infix notation. There is an

algorithm to calculate infix expressions as well, and it requires two stacks: one for numbers

and the other for operators.

Decisions are made based on the next input token T (either a number, an operator or EOF)

and the top of the operator stack as follows:

while T is not EOF or the operator stack is non empty

if T is a number:

push T to the number stack; get the next token

else if T is a left parenthesis:

push T to the operator stack; get the next token

else if T is a right parenthesis:

if the top of the operator stack is a left parenthesis:

pop it from the operator stack; get the next token:

else:

pop the top two numbers and the top operator

perform the operation

push the result to the number stack

else if T is +, – or EOF:

if the operator stack is nonempty and the top is one of +, -, *, /:

pop the top two numbers and the top operator

perform the operation

push the result to the number stack

else:

push T to the operator stack; get the next token

else if T is * or /:

if the operator stack is nonempty and the top is one of *, /:

pop the top two numbers and the top operator

perform the operation

push the result to the number stack

else:

push T to the operator stack; get the next token

Your task for this problem is to code this algorithm in C++.

Specification

• Your program will evaluate a single well-formed arithmetic expression from standard

input, and display the result on standard output.

• You will implement the algorithm given above. The point of this problem is for you to

use a stack to solve a problem. If you decide to solve this problem by making a system

call, or by writing your own parser, etc, you will receive a grade of 0 for this question.

• All input numbers are positive integers. Thus you will do integer arithmetic.

• Your program may assume the input is well-formed, i.e., the behaviour may be indeterminate on incorrect input (bad infix expressions).

• Name your file eval.cpp and submit to CourSys.

Some Help

• You are provided a Scanner class that produces Tokens for you. Please read Scanner.h

to see what objects of type Token look like.

• You will use the provided Stack for both your number stack and operator stack. Please

check the documentation for the behaviour of .pop() before using it.

• There are a few sample expressions provided to you to torture test your code. You

should come up with some of your own test cases as well.

4. [30 marks] Augmenting a Queue (Circular Array)

Included in your care package is the implementation of a Queue ADT by a static array

(circular array). If you build and run the test driver as it is, the queue won’t be big enough

to handle all the elements: some elements will be lost due to an overrun. You could rebuild

the code for a different value of INITIAL_SIZE, but that won’t work in every case. If you

need something that can grow to an appropriate size, a static array won’t do.

If you recall the capacity attribute from Assignment 1, this is where it will come into play.

The strategy will be to augment the Queue so that the capacity may grow as needed.

(a) Open Queue.h and change the static array declaration to a pointer int * arr. Next,

update the constructor in Queue.cpp so it dynamically creates the array.

(b) Classes that use dynamic memory also need a destructor. You should add it now.

(c) Resizing the array is a relatively expensive operation. You need to find a larger space,

copy the elements from the old array into the new array, and recycle the old array.

Overall, this is an O(n) operation, and should occur sparingly. One effective strategy

is to double the capacity of the Queue whenever you enqueue into a full array. The

expensive resizing operations are amortized across enough operations that they don’t

become an issue. (For more detail, please read the Appendix on expandable arrays.)

Implement this strategy by re-writing .enqueue(x).

(d) To have an array that has too large a capacity compared to the number of elements is

also bad. It is a waste of space. One good strategy is to halve the capacity of the Queue

whenever the array is less than 1/4 full. However, the min capacity cannot drop below

the value of INITIAL_SIZE.

Implement this strategy by re-writing .dequeue().