Assignment 1

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: 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: 20pt, Question 1b: 20pt - 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.

In this assignment, you are given the main program 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.

3. Question 1a

Using the given type definition for `stack' implement the abstract data type `stack' specified in class.

4. Question 1b

Write a procedure called read_and_evaluate_expression that reads in a evaluates a postfix expression (defined below) and writes out its value.

Your procedure must follow the algorithm sketched below, and it must use your implementation of abstract `stacks'. But the procedure should not depend on the details of your particular implementation - the procedure should depend only on the specification of abstract `stacks' and therefore should work with any implementation of the specification (The TAs might check this by using their own stack implementation instead of yours).

The main program is a loop that calls read_and_evaluate_expression repeatedly. When the user wants to quit, s/he should be allowed to take some action to the program about it. read_and_evaluate_expression should watch for, and be able to recognize this action. Furthermore, it must return a boolean that is true unless the user has just taken said action.

Check out the programming tips below for some ideas on how to do that.

5. Postfix Expressions

A postfix expression has the form X1 X2 X3 ... Xn where each of the Xi is either a single digit (0...9) or one of the following binary operators: +, -, *, / (the operator / means integer division).

We adopt the convention that a postfix expression fits entirely on 1 line of input. In other words, the newline character, written '\n' in C, indicates the end of the expression.

Should you find it convenient, you may also assume that X1 is the first character on the line, and that each Xi is separated from the next by exactly one space (i.e. ' ' in C).

The expression is postfix because an operator is written after its two operands. For example, the normal (infix) expression 2+3 would be written 2 3 + in postfix. Postfix has the advantage that parentheses are never needed. In infix, one expression (e.g. 2+3*4) can have several possible meanings (e.g. (2+3)*4 and 2+(3*4)) and parentheses (or precedence conventions) are needed in order to distinguish among the possible meanings. In postfix, each expression has a unique meaning. For example, (2+3)*4 would be 2 3 + 4 * in postfix, whereas 2+(3*4) would be 2 3 4 * +.

6. Algorithm for evaluating postfix expressions (Sketch)

There is one stack for holding operands, call numbers, which is initially empty.

Example: input line is 2 3 4 * + 5 -

7. Programming Tips

Reading Characters From The Input

In C, you may read the next character available from the input by calling getchar(). Surprisingly enough this function does not return a value of type char, as you might reasonably expect, but of type int. The reason for this is that it is thus able to return special values which do not correspond to any character code. For example, EOF (which is often defined as -1) indicates that no character could be read because e.g. the End Of File was reached.

Printing Messages And Integer Values

The function printf is used for printing purposes. It takes 1 or more arguments. The first argument is a string that describes what to print. In the simplest case, it is just a string and there are no other arguments:
        printf("Hello World!\n");
Notice the newline character embedded in the string. The string may also contain embedded directives to print other values:
        printf("You weigh %d kilograms\n",67);
causes the following line to be printed to the output:
        You weigh 67 kilograms
The %d directive is for printing values of type int.

Converting Digit Characters To Integers

In C, the notation 'A' denotes the code used to represent the character `A'. The value of this code is an integer. In ASCII, i.e. the American Standard Code for Information Interchange, the code for 'A' is 65, and the code for '3' is 51, and not 3 like you might have assumed.

Therefore, some work is required in order to turn a digit character such as '3' into the corresponding integer, i.e. 3. As it turns out, in ASCII, the natural sequence of digits is mapped to a corresponding sequence of codes. Therefore, in order to determine the integer value of a digit character, all we need is to compute its offset from '0'. E.g. '3' - '0' == 3.

Quitting From The Program

The skeleton program which you are given contains an infinite loop that repeatedly prompts the user for an expression and invokes your function read_and_evaluate_expression to evaluate it.

It is desirable to allow the user the option to quit from this infinite loop and exit the program. For this purpose, we require read_and_evaluate_expression to return a boolean that indicates whether the main program should loop again.

It is up to you to write your function so that it returns false when finally the user wants to quit. Here are some options:

Traditionally, at least on UNIX systems, Control-D is used for this purpose. Typing Control-D causes the input stream to your program to be closed. When subsequently your program invokes getchar() to read from its input, the special value EOF (for End Of File) is returned.