Project 3 — A Fractional Desk Calculator

Assigned	Tuesday, October 28th^th
Program Due	Friday, November 7^th by 11:59pm
Weight	8%
Updates	None yet.

Objectives

To gain experience:

Writing a class according to a predefined specification
Overloading operators in C++
Creating a complex numerical algorithm

Project Policy

This project is considered an CLOSED project. Please review the open vs. closed project policy before beginning your project.

The Fractional Desk Calculator

You will be developing a desk calculator to accept and compute the solution to fraction-based equations. It will do the usual addition, subtraction, multiplication, and division operations, but will work on full, general-form fractions. Even most smartphone calculators won't accept that! Also, your calculator will accept complex, nested expressions, with parentheses. On top of all this, it will accept input in a cool format called "prefix notation", different from the "infix" notation most boring calculators use. Here is an example of prefix notation:

( * 2 ( + 3 4 ) )

Try to predict what this will yield. Prefix notation will be coverd in more detail later.

There will be one more feature to your calculator: It will accept AND PRESERVE the exact form of fractions as input by the user, but all calculated values returned by the operators will be in a strictly normalized form. In other words, it will be nice to the user and kindly reduce all computed terms to a more friendly form, taking care of both minimizing and factoring the fractional part of the number, matching the signs, etc. An example would be: An input (and therefore construction) of "4/3" stays as 4/3, but adding 0 to it would result in 1 1/3. The exact details are given later.

For your part of the project, you will be coding up the guts of the computational part of the calculator. We will be providing the part of the code that accepts and interprets the user input, and dispatches to the appropriate functions in your classes. For this project, we will need a very important type of program known as a "parser". A parser is a program that takes a stream of input, breaks it up into smaller components, infers the value and purpose of each component, and executes a specific sequence of tasks. For example, a C++ parser would take the sequence of characters that make up your source file, and figure out what you want your program to do. Parsers are often very difficult to write. However, it is much easier to understand one than to create one on your own, which is why we provide one to you. It is definitely worth looking through our code to learn how a simple parser works, so we would highly encourage you to try to understand the details.

So, we provide the U/I and parser, and you are responsible for creating a Fraction class that can support the required arithmetic operations, as well as normalization. Simple enough? No so fast...

Since you've just learned about operator overloading in class, it is time to apply it on a project, and a calculator is a perfect fit for overloading the arithmetic operators. If you look through the provided code, you will see a section where we first figure out which operation the user wants to do (addition, subtraction, etc.), and then do that operation on the operands. However, both operands are instances of your Fraction class, and our code simply takes these operands and, instead of invoking named methods like: sum = operand1.AddFraction(operand2); it expects you to have set things up so that it can use an overloaded addition operator, thus:

    result = operand1 + operand2;
    // and later:
    cout << result;

But since operand1, operand2, and result are all instances of the Fraction class, you will have to get C++ to accept those as legal operands to its '+' operator, and get cout to accept Fractions as parameters: operator overloading to the rescue!

The Calculator U/I

Three things to point out about the calculator's U/I: First, it uses an input format called "prefix notation": that means the operator comes ahead of the operands, i.e. is written as a prefix to the operands. This is different from the way we usually write expressions, in "infix notation", where the operator is embedded between the operands:

Infix: 3 * 4
Prefix: ( * 3 4 )

You probably noticed the '(...)' we threw around our simple expression above. This points out the second requirement on our calculator's input format: all subexpressions must be parenthesized. So, we have the following equivalents:

Infix: 3 * 4 + 9
Prefix: ( + ( * 3 4 ) 9 )

The nice thing about prefix notation is that we've removed the need for any notion of operator precedence or associativity; that's why we chose it.

The third point: in order to keep the parser code simple, we require spaces around all of our operators and parentheses, but require an entire fraction specification to be concatenated together without any embedded whitespace:

Bad: (*3 -17 & 36 / 12)
Good: ( * 3 -17&36/12 )

Please follow that rule. By the way, the above expression would be equivalent in infix to: "3 * -20" == -60.

Project Requirements

You will be creating a class called Fraction, which implements the Fraction class that supports the storage as well as arithmetic manipulation of numerical fractions. It will model a Fraction as 4 parts: a an optional sign; a whole-number part; a numerator; and a denominator. The sign applies to the entire number; so, "-3&6/2" is equivalent to -6. The user is allowed to enter any value for any of these parts, with the one restriction that the denominator must not be 0 (zero).

We will introduce here the input format for fractions in our desk calculator, because it is conveniently also a precise way for us to specify fractions in our examples in this project specification. A fraction will be a contiguous "no whitespace" string, in the following format:

An optional sign: either '+' or '-'.
An optional whole-number part: an unsigned integer;
An optional fractional part: two unsigned integers, separated by a '/' (forward-slash)
If there is both a whole-number and a fractional part, they must be separated by an '&' (ampersand). (Note that we distinguish a "fraction" from the "fractional part" of a fraction. Confusing, we know, so we'll try to be very consistent.)

NB: the optional sign applies to the entire fraction: "-1&2/2" would be equivalent to "-2". The parser separates out the sign part, and passes it in as a separate boolean input parameter to the constructor (it is the first parameter), "true" if the user entered a leading '-' sign.

So, some legal fractions are:

2
1/3
2&5/6
-2&21/6 (== -5.5)
-7/2 (== -3.5)

The Three Components of your Fraction Class

There are three important components to your Fraction class implementation:

1. The Representation:

Your Fraction class needs to represent numbers exactly as entered by the user, i.e., exactly as passed to your constructor. That means the numerator can be larger than the denominator, and it is not reduced to the lowest common denominator (i.e., 4/6 is not reduced to 2/3). Note that you need to keep track of, and manage, the sign of the fraction.

The only thing your constructor should reject is a 0 for the denominator: if your constructor is called with that, you should print out an error and exit.

Your default constructor should create a Fraction of 0&0/1

2. Fraction Normalization

Normalization is the process of converting a more free-form value into a more structured form that follows a specific set of rules/restrictions. While you are required to leave user-created fractions as-is, the results of any calculations (described in the next section) should be in what we call strict normal form. This means the parts of the fraction need to be adjusted, without altering its implicit numerical value, to meet the following criteria:

denominator > 0
|numerator| < denominator
fractional part is reduced to lowest terms (e.g., 3/9 -> 1/3)
if (numerator == 0) denominator set to 1

So, applying the rules, "2&15/6" would be normalized to "4&1/2".

3. Operator Implementation

You will be implementing the 4 basic arithmetic operations for Fractions, as well as the output function. That means you will need to write code to implement things like multiplication and subtraction between Fraction objects. Also, you will need to overload the '+', '-', '*', '/', and '<<' operators, in order to allow the code in Proj3Aux.cpp to compile and work.

Provided Code

We are providing far less design guidance on this project than on previous ones. For example, we are not providing a header file for the Fraction class. Look through our provided code to see what kinds of constructors we require (hint: you will need at least two). Again, we'll remind you that one of the parameters to the full constructor will be a boolean flag indicating the sign of the fraction (i.e., whether the user entered a leading '-'). You must handle that appropriately.

Other than that, you will need to provide functions to overload the four arithmetic operators and the "<<" operator, and that's about it for the public interface for your Fraction class.

You are free to add any helper functions you'd like to make the Fraction class more modular and cleaner in design.

The only files we are providing are:

Proj3.cpp: contains a simple main()
Proj3Aux.h: There two files implement the parser
Proj3Aux.cpp: Actual code for the parser

Example Session

The program takes no command line arguments. It goes into a contiuous loop, prompting for an expression, reading it, parsing it, performing the required operations, then outputting the results. It exits on end-of-file (ctrl-D on Unix and Macs). If the input expression is malformed, it tries to point out where the problem was (with limited success, unfortunately). Here is a sample run: (Note: the text the user entered is in red. Also, the lines that begin with "//" are not actually part of the run--just annotations I added afterwards.)

$ ./Proj3.out
// Some simple numbers: first a whole, then fraction, then  mixed.
> 1
1&0/1
> 2/3
0&2/3
> 1&2/3
1&2/3

// Now, some strange cases.  Notice following is not normalized,
// because it is merely constructed, and no arithmetic has been done yet:
> -2&15/6
-2&15/6

// Now, to see normalization in action: taking the same number
// as above, but add 0 to it to trigger normalization:
> ( + -2&15/6 0 )
-4&1/2

// Another normalization example:
> ( + 1&2/3 2&1/3 )
4&0/1

Note the answer is not 3&3/3, nor is it 4&0/3

How to Test Your Project

You should throughly test your program for all typical, edge, and error cases. The example above does some of this. You should test all possible combinations: mixing positive and negative fractions in your operations, sticking in 0's for various parts, including the denominator; entering just whole numbers; having numerators > denominators; doing operations that cancel out to very simple results after normalization, etc..

How to Start

You should probably first start with the constructors. You should then be able to test the program by just entering a fraction into the calculator, and making sure it prints out exactly as entered.

You should then add the overloaded operator functions,, starting with "<<". This one, you need right away, but it is really easy to implement: one or two lines of code. Note the following, though:

You should then move on to the overloaded arithmetic operators, but not actually implement the bodies yet. Just have them print out their operands, and then return an innocuous result (e.g., just construct a default 0&0/1 and return it). That way, you can test that the operator overloading is being called properly. Remember, the calculator's parser code cannot tell whether you're passing back numerically correct answers, so 0&0/1 is always a fine return value. It only demands that they be Fraction instances.

Next, you should actually implement the guts of the four operations, working on and debugging one at a time. After the '+' operator, '-' should be easy; same with '*' and '/'.

Lastly, work on the normalization code. Note that to implement this, you will probably have to implement algorithms to calculate the greatest common divisor (GCD) and lowest common multiple (LCM) of two numbers; brief outlines are given below.

Some Helpful Algorithms

Greatest Common Divisor: Euclid's Algorithm

A simple way to compute the greatest common divisor of two integers, credited to Euclid, is the following iterative algorithm:

Step 0: Order the two numbers x and y so that x holds the larger number.
Loop:
- Step 1: Divide x by y, storing the remainder in r
- Step 2; If r == 0, return y
- Step 3: Shift the variables: x = y, y = r

That's it! Try working through the algorithm manually with the numbers 21 and 6 to convince yourself it works correctly (the answer should obviously be 3).

Least Common Multiple

Once you can compute the GCD of a pair of numbers, calculating the LCM is very simple: the LCM is computed as:

$\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}.$

(courtesy of Wikipedia)

Additional Requirements

As always, you will have to create a Makefile.

Grading

See the course website for a description of how your project will be graded.

We will be automating much of the grading for this project. It is absolutely essential that you do not modify any of the files that we provided to you; You should not even submit these files. If you do inadvertantly submit your copies of these files, we will be replacing them with our own versions before trying to compile and run your program.

Another requirement is that your executable, as produced by your Makefile, is called Proj3.out; adjust your Makefile accordingly.

Project Submission

Before submitting your project, be sure to compile and test your code on the GL system. See the Project Compilation section of the course Projects page for details on how to compile and execute your project on GL.

Assuming you’ve used the specified file names, submit your project by typing the command

submit cs202 proj3 [all of your various .h and .cpp files] Makefile

See the Project Submission page for detailed instructions. Note that we require you to submit the Makefile, also. We will in fact be using your own Makefile to build your program, so it must work properly.

You may resubmit your files as often as you like, but only the last submittal will be graded and will be used to determine if your project is late. Also note that if you rename or remove certain files, the old versions that you submitted earlier will stay in the submit directory unless you use "submitrm" to clean them out, which you should. At the end, a "submitls" should show exactly those files that are part of your project: no more, no less. For more information, see the Projects page on the course web site.

Remember — if you make any change to your program, no matter how insignificant it may seem, you should recompile and retest your program before submitting it. Even the smallest typo can cause errors and a reduction in your grade.