Skip Navigation CECS Home | ANU Home | Search ANU

Introduction to Computer Systems

Assignment 2 Specification - rPeANUt - Reverse Polish Calculator

The aim of this assignment is to give you a challenging assembly program to write. Unlike the first assignment, this assignment will be completely marked by computer. Thus the focus is on correctness and performance. Coding style and coding formatting will not be marked (not to say these are not important as a clear consisted approach in your formatting and coding style will help with the correctness of your submission).

The basic part of the assignment aims to be simple enough for most students to be able to complete in less then 5 hours. The assignment also aims to provided a more challenging programming task for the student who wish to gain extra experience (and a higher mark).

The assignment will be marked out of 100. And is worth 10% of the final mark. A late penalty of 10% per day applies (these are working days and apply from after the assignment is collected. The assignment will be collected some time after noon on the Friday. Also note this penalty is caped, so it does not take your final mark below 40 out of 100. Assignment work will not be accepted after the last day of semester. Extensions are possible in documented exceptional cases (e.g. medical certificate).

Reverse Polish Calculator

The calculator program takes input commands from the terminal and uses these to calculate a result. This is done one line at a time. An empty line halts the program.

Expressions are given as a list of space separated numbers or operators. The new line signifies the end of an expression and that the expression should be calculated with the resulting value returned to the terminal. These expressions are in reverse polish form (see http://en.wikipedia.org/wiki/Reverse_Polish_notation). You may assume the input provided to the program has no formatting problems. You may also assume that all the numbers given to the calculator (or used in a partial calculation) will be represtable via a 32 bit signed integer.

If you type the below into the terminal (the last line is empty making the calculator halt):

2 4 +
4 1 4 + -
-3
-1 -1 *
4 2 * 7 +
4 2 /
4 2 %
5 !
2 10 ^

then you would expect the flowing output:

6
-1
-3
1
15
2
0
120
1024

Such a calculator can be implemented by making use of a stack. An expression is parsed from left to right and there are basically three situations. Firstly, if a number is encountered then that number is pushed onto the stack. Secondly, if a binary operator is encountered (+, -, *, /, %, ^) the top two numbers on the stack are popped off which are used by the binary operator and the result is pushed onto the stack. Thirdly, if a unary operator is encountered (!) then one number is popped, applied to the unary operator, and the result is pushed onto the stack.

The operators you need to implement are:

• + addition
• - subtraction
• * multiplication
• / integer division (you may assume that the divisor is positive)
• % integer remainder (you may assume that the divisor is positive and the dividend is non-negative)
• ^ power (you may assume that the exponent is non-negative)
• ! factorial (you may assume that the number operated on is non-negative)

Note, you may apply optimisations, however, any changes must result in the same evaluations of the expressions.

Marking

The marking of this assignment will be automatic. So it is important that your solution compiles and works. Also, get the assignment working in stages. Different tests will be performed such that if you only complete some of the assignment you will still gain marks for the parts you get working. If you can't get the harder parts of the assignment working just leave them out of your submission and get the marks for the earlier parts. The marking stages of the assignment are as follows:

1. Your program compiles. [10 marks] (Note - submit an empty file and you will get 10 marks for the assignment!)
2. Halt works. [10 marks]
3. single number expression (one line) [10 marks]
4. single number expressions (multiple lines) [10 marks]
5. adding [10 marks]
6. subtraction, multiplication, division, remainder [10 marks]
7. factorial [10 marks]
8. power [10 marks]
9. Performance. [20 marks] This requires all of the other stages working correctly. Basically your submission will be benchmarked (in terms of the number of steps it takes to run) against my solution for a particular input. The final test in the tests below give you an idea of the types and amounts of commands issued for this performance test. However, the actual performance test will not be identical.

Stages 4+ also require the multiple line and halt to work.

Tests

Some test sets are available to give you an idea of the type of automatic testing that will be done on your solution. All marks will be done via this automatic testing so you need byte identical solutions.

Tests are available from: http://cs.anu.edu.au/students/comp2300/ass2tests (or as one tar file alltests.tar). These give you an idea of the types of tests performed.

To run a test you need to check that when your program is given a set of commands it produces identical output. This can be done using the following terminal command:

java -jar rPeANUtxxx.jar yoursolution.s < testX.rp | diff -s - testX.rp.res

There should be no difference between your output and what is expected.

Individual Assignment

This is an individual assignment. You may help each other, however, the final submission must be original and your own work. Take care not to give parts of your solution to other students.

Assignment Submission

The assignment must be submitted via a computer in the CSIT labs (or remotely via ssh to "partch" or one of our servers). To submit the assignment use the following command:

submit comp2300 ass2 calculator.s

A few hits for submission:

• Don't have spaces in your file names. (the submit program does not like them!)
• Copy the files to your home directory, rather, than having them mounted on a USB drive.
• You may submit as many times as you like, I will mark the most recent one that is not late.
• If you are in comp6300 then use comp6300 rather then comp2300 in the command.