Project 3 — A Fractional Desk Calculator

Assigned Saturday, March 29thth
Program Due Thursday, April 10th by 11:59pm
Weight 8%
Updates None yet.

Objectives

To gain experience:

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

Project Policy

This project is considered an CLOSED project. Please review the open 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: -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...

The problem is, after hacking all night on the parser code, your instructors got very tired and needed a nap, so we decided we didn't feel like typing in long function names, and took a shortcut. However, we didn't want to set a bad example by just resorting to using short, cryptic function names that would violate the class coding standards. Instead, we decided to take advantage of operator overloading, especially since it seemed like such a good fit to the problem.

If you look through our 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 we want you to implement that class so that we don't have to do the usual: result = Fraction::AddTwoFractions(operand1, operand2); You might suggest: result = operand1.AddWith(operand2); But the instructors find even that too long to type in. We want to write our code as: 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

Two things to note 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.

One last thing to point out about our calculator U/I is that, 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 * -14" == -42.

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 3 parts: a whole-number part, a numerator and a denominator. All three parts are signed integers. 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 whole-number part: an integer with an optional leading sign; An optional fractional part: two signed integers, separated by a '/' (forward-slash) If there is both a whole-number and a fractional part, they must be separated by a '&' (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.)

So, some legal fractions are: 

2
1/3
2&5/6
-2&-21/6 (== -5.5)
-7&6/-2  ("negative 7 and 6 negative-halves), i.e., == -10)

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. Note how wacky the last example above is (-7&6/-2). However, it is perfectly legal. Your Fraction class should be able to store that exactly as specified, with a negative whole-number part and a negative denominator.

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:
  1. denominator > 0
  2. sign(numerator) == sign(whole) (a 0 matches either sign)
  3. |numerator| < denominator
  4. fractional part is reduced to lowest terms (e.g., 3/9 -> 1/3)
  5. if (numerator == 0) denominator set to 1
So, here are two examples, showing the application of each rule in turn: 
4&22/-8 -R1-> 4&-22/8 -R2-> 1&2/8 -R3-> 1&2/8 -R4-> 1&1/4 -R5-> 1&1/4
2&-28/7 -R1-> 2&-28/7 -R2-> 0&-14/7 -R3-> -2&0/7 -R4-> -2&0/7 -R5-> -2&0/1
You do not have to apply the normalization rules in the exact order listed above, as long as the results follow all of the rules.

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). 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.

Additionally, you are free to add any helper functions to make Fraction more modular and cleaner in design.

The only files we are providing are:

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 not the result of a calculation
> -1&-2/-3
-1&-2/-3

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

// Another normalization example: note following is not 3&3/3
> ( + 1&2/3 2&1/3 )
4&0/1

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 whole-numbers, numerators, and denominators; 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: 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.