Assignment 2

You should say this in class regarding this assignment:

Explain the type definitions. Also the types of the operations.

Explain the memory_count business.

Emphasize that the application program will work equally with any implementation of stacks - students should convince themselves of this by trying it out on the array-based implementation they did for assignment #1. And also, they should take their application program from assignment #1 and sit it on top of their stack implementation for this assignment. It ought to work first time.

Due date:

Late assignments will be penalized 10% per day, and will not be accepted after .

1. Hand In

Each student is required to do this assignment individually and to hand in the following:

A disk containing only two files: the source listing and executable for the program in the assignment.
Printouts of the program and the output it produces in test data of your own choice.

Place these items in a 9"x11" envelope, with the following information clearly marked on the outside of the envelope:

Name, Student Number, Assignment Number, Course Number (T26)

Assignments which are not in an envelope will not be marked

Deposit your envelope in .

Marking Scheme

Programming standards: 10pt, Question 1a: 10pt, Question 1b: 30pt - Total: 50pt.

Your program must conform to the programming standards. These are described in a separate sheet.

2. Program Handout

In this assignment, and others in the future, you will be given part of the final program and your job is to write the remaining parts of the program.

You must use the given parts of the program without changing them. For example, all memory management must be done using the given procedures get_memory and return_memory - do not directly use C's built-in procedures malloc and free.

In this assignment, you are given the main program, the memory management procedures, and a type definition of `stack' (and related types). These are available on a disk file that you can copy (so you don't have to type it in) - ask your teaching assistant where and how to obtain this.

Note that the main program writes out the variable memory_count as its last action. If this value is not 0, you have bugs to fix.

3. Question 1a

Design the implementation of the push operation using before and after node-and-arc diagrams, as described in class.

4. Question 1b

Using the given type definition for stack implement the abstract data type `stack' specified in class. Unlike Assignment 1, this will be a linked implementation using C's pointers.

To test your program use the given main program and procedure called read_and_evaluate_expression. This procedure will work with any implementation of stacks that conforms to the specification.