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.