Assignment 1. CS330 Programming Languages, Spring 2004

A postfix calculator for rational arithmetic (5% of grade)

Assignment Description

PLEASE READ CAREFULLY - MISSING
LITTLE DETAILS MIGHT COST YOU

In this assignment the task is to write a program to perform artithmetic
of rational numbers using post-fix notation. The input to your program
will be a text file where each line contains one expression of rational
artithmetic in postfix notation. The goal is to write a program that outputs
to a file the result of each expression as a rational number.

A number q is rational if q = a / b where a,b are integers with b not equal to 0.
In the input text files, the rational numbers will be represented as follows:
1|2 (what we call one over two), 3|4, 20|10 etc. Notice the use of the bar | symbol
rather than the division symbol.

The two supported operations of our calculator are addition and multiplication denoted
by the usual characters + and *. In postfix (or reverse Polish) notation, the operator
follows the operand. For example  (5+4)*3 is written as 5 4 + 3 * and 5+4*3  is
written as 5 4 3 * +. A simple way to calculate the value of a postfix expression
is by reading the expression from left-to-right and storing each number in a stack.
Whenever you encounter an operator you apply it to the two top values of the stack
and replace them with the result of the expression. You continue that way until you
have processed all the input.

For example:
5 4 3 * +

stack 5
stack 5 4
stack 5 4 3
stack 5 12       (the result of applying * to 4 and 3)
stack 17          (the result of applying + to 5 and 12)


Your task is to do the same type of process with rational numbers and the following
two operators:

a|b  + c|d = ad + bc | bd       (rational addition)
a|b  *  c|d = ac | bd               (rational multiplication)

For example:
1|4 +  2|8 = 1*8 + 4 * 2 | 4 * 8 = 16 | 32
2|4  * 3|2 =  2*3 | 4*2 = 6 | 8

We also want the results to be simplified i.e 10|20 should be written as 1|2.
This can be accomplished by dividing the nominator and denominator with
their greatest common divisor (10 in our previous example) before printing the
result.

Input file conventions: whitespace (one or more spaces) separates the rational numbers
and operators  (Important there is no space between the nominator-bar symbol and
denominator). You can assume that the input is in the correct format although
some elementary error checking will be rewarded. The assignment is in two
parts. Part 1 is very simple and consists of only evaluating one operation/line
such as 1|4 2|8 +. In other words there is no need to use the stack. All you need
to do is parse the input and perform the right operation. This part will be worth half
the points of the assignment. Here is a test case for Part 1 with the correct output:

Part 1 example input file
Part 1 example output file

Part two consists of adding the stack for evuating arbitrary postfix expressions.
Your program should be able to handle as many numbers/operators as provided
in the input. (in other words make no assumptions about the stack size). Here
is a test case for part two with the correct output:

Part 2 example input file
Part 2 example output file

Make sure you try other test cases in addition to these examples.

Practical matters 

You may use any programming language you want. You must submit the full
source code plus a README.txt file describing how to compile and run your
program. I have a preference for commandline compilers but if you are
using some programming environment such as Visual Studio you are welcome to
do so. If you do so then I would like an executable version of your code for any
of the following operating systems (Windows, Linux or OS X). WARNING
if the executable doesn't correspond to the source code provided then you will
fail the assignment completely even if it works perfectly. There might
be other consequences so DON'T EVEN THINK about giving the wrong executable.
The executable should take as arguments the names of the input and output file.
For example I should be able to run it as:

mycalc input10.txt output10.txt

If you are using a standard widely available tool such as gcc or javac then you
can provide just the source code with instructions of how to compile it.

Check the course web page for submission instructions (should be
similar to the web submission system you have used for
other courses) and if you run into problems email me and we will figure it out.

Late assignment policy:  If the assignment is submitted
within three days from when it was due, you will get half the grade you
would get if you had submitted on time. You will not be able
to submit after three days. (exceptions to this rule only
if you have a VERY important reason).

IMPORTANT: The careful design and documentation (i.e comments) of
your code will be important factors in your grade. If there is a bug
it's better to report it than hide it. Be honest, precise and clear and
you shall be rewarded. NEVER (at least in this class) sacrifice
clarity for efficiency of execution.

IMPORTANT: If you have a hard time writing or understanding
this assignment then you will probably find CS330 is most likely
too advanced for you and will require extra effort and time.