ACM Regional Programming Contest 1998

Problem No.  2  - Fraction Calculator

Source Program:

The problem:

You are to write a four-function rational-number calculator. That is, given an input string consisting of decimal integers, four binary operators (+,-,*,/), and one unary operator (-), your program is to perform exact arithmetic and print the result as a fraction in lowest terms.

To provide as much flexibility as possible for the calculator's users, the input you will have to handle does not need to follow a particular format. Because entering a calculation sends it to be evaluated, you will process each line of input separately. This line of input is evaluated in the usual way, i.e., unary - has highest precedence; * and / have equal and secondary precedence, and + and - have equal and lowest precedence. Equal precedence operators are evaluated from left to right. If the input does not yield a valid rational value (either because it is not an evaluable expression or because there is a divide by zero), your output should be the line

Not a valid input.

Whitespace may separate any of the tokens in an input line (of course, numbers of more than one digit will not contain whitespace).  All input integers will be in the range between -999 and 999, inclusive. In the output, there should be no spaces and the result should be in lowest terms. Denote integer outputs n as n/1 and indicate negative results with a negative numerator.

Sample Input:

3/12 - 4/8
3/4 -
1 / 2 + - 4 / 3
1/2 - 10/5
5/6 / --3/4

Sample Output:

Not a valid input.