Due date:
Late assignments will be penalized 10% per day, and will not be
accepted after .
Name, Student Number, Assignment Number, Course Number (T26)
Assignments which are not in an envelope will not be marked
Deposit your envelope in .
Your program must conform to the programming standards. These are described in a separate sheet.
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.
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.
+, -, *,
/ (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 * +.
numbers,
which is initially empty.
numbers
stack.
op -
since it is a binary operator, it requires two arguments:
numbers;
call the first one removed R and the second
one L.
L op R and push the result onto
numbers.
numbers. We write it out and return.
Example:
input line is 2 3 4 * + 5 -
'2', push it onto numbers.
'3', push it onto numbers.
'4', push it onto numbers.
'*'. Pop numbers:
R=4. Pop numbers: L=3.
L op R = 3 * 4 evaluates to
12. Push 12 onto numbers.
'+'. Pop numbers:
R=12. Pop numbers: L=2.
L op R = 2 + 12 evaluates to
14. Push 14 onto numbers.
'5'. Push it onto numbers.
'-'. Pop numbers:
R=5. Pop numbers: L=14.
L op R = 14 - 5 evaluates to
9. Push 9 onto numbers.
numbers to get final
answer 9 and write it out.
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.
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.
'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.
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:
Y/N
answer to the question ``Do you want to continue?''. Of course,
this is rather tedious.
Q' (for Quit) or
EOF (see below).
getchar() to read from its input, the special value
EOF (for End Of File) is returned.