CMPT 225 Assignment 2


5/5 - (3 votes)

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 and unzip it. It contains your base code.
1. [30 marks] Static Array Stack
The overall goal of this question is to implement a Stack ADT using a static array where
• all k stack elements are stored sequentially in indices 0, 1, . . . , k − 1 of the array; and
• the topmost element is pushed to index 0 of the array.
This will be different than the typical implementation where the elements were pushed to the
other end of the array.
We’re not suggesting this is a particularly good choice of implementation, that is, it will force
at least one of push/pop to have a linear number of steps, where usually it would be O(1).
What You Need to Write
You are going to complete the implementation of a Stack ADT with a concrete data structure.
That data structure is a static array as described in the preamble. A new Stack has no
elements. Pushed items are inserted at index 0, and likewise, popped items will be removed
from index 0.
You will write reasonable descriptions, preconditions and postconditions. Should any of
.push(x), .pop(), .peek() violate a precondition, your method should trigger an exception
of type std::logic_error, with an appropriate error log message of your design.
Students who submit an alternate implementation will receive 0 for this question.
Complete your implementation in Stack.h and Stack.cpp, and then submit them.
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. State your conclusions using the big-O notation.
A detailed analysis is expected, i.e., if you present a final big-O answer only, you will be
unhappy with your grade. Submit your analysis in Analysis.pdf.
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:
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
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
push T to the operator stack; get the next token
At the end of the algorithm, there should be a single number on the number stack. That is
the computed answer.
Your task for this problem is to code this algorithm in C++.
• 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 it for grading.
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 for our Sequence implementation, this is where it will
come into play. The strategy will be to augment the Queue so that the capacity may grow
as needed.
Note: Because you are working with dynamic memory, it’s important you don’t leak memory—
so important that it’s required. The graders will test your implementation using valgrind,
and so should you.
(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) Classes that have a destructor should generally perform a deep copy on a copy constructor and on assignment. Complete these methods next.
(d) 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.
Implement this strategy by re-writing .enqueue(x).
(e) 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().
(f) Finally, add exceptions of type std::logic_error in cases where preconditions are
— ©2022 Brad Bart, Simon Fraser University, Canada

Scroll to Top