Project 3 — A Fractional Desk Calculator

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

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

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 )

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

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

1. The Representation:

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

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

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

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

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:

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

Example Session

$ ./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

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

• 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

Least Common Multiple

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.