Hunter Liu's Website

16. Week 8 Thursday: Practise with Structs

Last discussion, we saw an example of how to use structs to neatly package multiple variables into a single bundle. On the pseudocode side, these structs are complex nouns that have multiple simple attributes; treating each attribute as a separate variable in code can lead to a lot of horrible problems.

Let’s get some more practise with writing our own structs and implementing their member functions.

SAMPLE RUN 
----------
INPUT   2
INPUT   1/2 1/6
OUTPUT  2/3

INPUT   2
INPUT   2/5 3/5 
OUTPUT  1 

It’s very possible to do this without implementing a struct at all. However, the point of this is to get some practise writing and designing structs yourself. Even if you are averse to object oriented programming, I would encourage you to work through this problem as intended rather than finding a workaround.

Let’s start by writing some pseudocode. This pseudocode is really similar to finding the sum of a bunch of numbers input by the user, but rather than decimal or integer inputs, the user is giving us fractions.

1. Take an integer n as user input.
2. Initialise a fraction total = 0.
3. Repeat n times:
   • Read a fraction frac as user input.
   • Add frac to total.
4. Reduce frac to simplest terms, then print it to the screen. If the denominator of the reduced fraction is just 1, then print only the numerator.

As with last time, we should identify that a “fraction” is a complex noun that represents an amalgam of simpler data, namely a numerator and a denominator. We can write code that handles these two integers separately, but this will cause our code to resemble our pseudocode very little.

So, let’s think about:

1. What is a fraction?
2. What can a fraction do?
3. How do we construct a fraction?

These correspond to what our member variables, member functions, and constructor(s) should be.

1. A fraction is a numerator and a denominator, so our member variables will be just two integers.
2. I need to be able to add a fraction to another fraction, I need to reduce a fraction to simplest terms, and I need to be able to print out a fraction to the console.
3. I can’t make a fraction without a numerator or a denominator, and there don’t seem to be any reasonable “default values” that I can assume. I should therefore provide both the numerator and the denominator when I make a new fraction.

As soon as we’ve written down this information, we can write out the header file (i.e., the definition of the struct), even if we don’t immediately know how to fill in these member functions or this constructor.

 1#ifndef FRACTION_HPP 
 2#define FRACTION_HPP 
 3
 4using namespace std; 
 5
 6struct fraction {
 7    // member variables - a numerator and denominator
 8    int numer, denom;
 9
10    // member functions - add things in, reduce the fraction, 
11    // or print to the screen 
12
13    // adds another fraction to this fraction 
14    void add(fraction other); 
15
16    // reduces this fraction to its simplest terms
17    void reduce(); 
18
19    // prints out this fraction to the screen
20    void print(); 
21
22    // constructor - need a numerator and a denominator 
23    // in order to create a new fraction. 
24    fraction(int _numer, int _denom); 
25}; 
26
27#endif 

Note that all three member functions are void functions — none of them return anything. However, the sole purpose of add and reduce are to modify the contents of the fraction they’re attached to, while the sole purpose of the print function is to…well, print them out. We don’t need them to return anything to us!

We are now ready to write up our main function, even though we haven’t implemented the constructor or any of the member functions. The reason is that the main function only needs to be aware of what these functions are and what they’re supposed to do; how this gets done is completely irrelevant!

 1#include <iostream> 
 2
 3#include "fraction.hpp"
 4
 5using namespace std; 
 6
 7int main() {
 8    // 1. take an integer n as user input 
 9    int n; cin >> n; 
10
11    // 2. initialise a fraction called total to 0. 
12    // that is, total = 0 / 1 (for instance) 
13    fraction total(0, 1); 
14
15    // 3. Repeat n times....
16    for(int i = 0; i < n; i++) {
17        // read a fraction from the user. 
18        // numer/denom 
19        int numer, denom; char slash; 
20        cin >> numer >> slash >> denom; 
21
22        // create a fraction to hold the user input 
23        fraction input(numer, denom); 
24
25        // add it to the total 
26        total.add(input); 
27    } 
28
29    // 4. reduce and print! 
30    total.reduce(); 
31    total.print(); 
32
33    return 0; 
34} 

Finally, we need to fill in the implementation file for fraction. Try doing this yourself, one function at a time, before peeking at the solution. Some things to think about while you’re at it:

• How do you reduce a fraction with a numerator of \(0\)?
• What happens if a user tries to create a fraction with a denominator of \(0\)? Is there a way to prevent this from ever happening?
• When reducing a fraction, do we need to worry about negative numerators or denominators? What about when printing out a fraction?

There are many ways to address the above considerations, and the following is only one of them. Test your code thoroughly to make sure it works!

 1#include <iostream> 
 2
 3#include "fraction.hpp"
 4
 5using namespace std; 
 6
 7void fraction::add(fraction other) {
 8    // formula for adding: a/b + c/d = (ad + cb) / bd 
 9    int new_denom = denom * other.denom; 
10    int new_numer = denom * other.numer + numer * other.denom; 
11
12    numer = new_numer; 
13    denom = new_denom; 
14} 
15
16void fraction::reduce() {
17    // if the numerator is zero, do nothing 
18    if(numer == 0) return; 
19
20    // if the denominator is negative, flip all signs! 
21    if(denom < 0) { numer *= -1; denom *= -1; } 
22
23    // look for the gcd of the numerator and denominator. 
24    int gcd = 1; 
25    for(int i = 2; i <= denom; i++) {
26        if(denom % i == 0 && numer % i == 0) {
27            gcd = i; 
28        } 
29    } 
30
31    // divide everything by the gcd 
32    numer /= gcd; 
33    denom /= gcd; 
34} 
35
36void fraction::print() {
37    // if the denominator is 1, print only the numerator 
38    if(denom == 1) {
39        cout << numer << endl; 
40    } 
41
42    // otherwise, print numer / denom 
43    else {
44        cout << numer << "/" << denom << endl; 
45    } 
46}