Exercises for Day 6

Write C++ programs for each of the exercises below. You should use only features in the language which have been discussed in the notes through this day.

Shorter Exercises

1. Simple Operator Overloading

Define a struct called “name” consisting of two strings, one for first name and one for last name. Allow comparisons of names alphabetically in the usual way (last name takes precedence over first name), by overloading the “<” operator. For simplicity, use the built in strcmp function rather than the APSTRING.

2. An Overloaded MAXSORT – Operator Overloading (*)

Let’s rewrite MAXSORT using operator overloading.

Recall that MAXSORT takes an array A of size strings and sorts it by swapping the largest ITEM in the first size strings in A, with the current last location. The current last location starts at size - 1 and size is decremented at each iteration until it equals 1. MAXSORT uses a MAX and a SWAP function. MAX takes an array A of size strings and returns the index of the largest string in the first size strings.

In the version from the Day 3 exercises, MAX used the strcmp function and SWAP used strcpy. Here however, MAX will use an overloaded “<” operator, and SWAP will use an overloaded “=” operator. The new MAXSORT will look syntactically like a sorting function for simpler types like integers or floats.

3. A More General MAXSORT – Function Templates (*)

Our goal is to write a general MAXSORT which can sort arrays of strings, integers, floats or other types. Since the MAXSORT, MAX and SWAP functions from problem 1 looks the same regardless of the type in the array, it is natural to write function templates for them, and thereby accomplish this goal. Use the function template for SWAP in chapter 3 as a model.

MAXSORT would then work on an array of any type, providing that the “<” and “=” operators have been overloaded appropriately for that type. Note the helpful relationship between operator overloading and function templates.

Test the program on both an array of integers and an array of strings.

4. Overloading Operators for the Members of the Complex Number Class (*)

a. Replace the add, subtract, multiply and divide member functions of the complex class (from the Day 5 exercises) by overloading the “+”, “-“ , “*” and “/” operators. We must change the first line of each member function, and change any references to member functions in the body of each function.

b. Overload the “<” operator to replace the print member function of the complex class, by using friends as done in this chapter.

c. Test the class with a main to compute and print: (1 – i) + (2 + 4i)/(9 – 6i) – (8 + 2i).

A Note Regarding the THIS Pointer:

Depending on how you previously implemented the member functions for the complex class, the THIS pointer, may allow simplifications. For example: If the divide function is implemented with two calls to the multiply function, the object invoking the divide function must also invoke the multiply member function in the body of the divide function. Without the THIS pointer, we must create a new copy of the object. However, these simplifications are conveniences rather than conceptual. Hence, this exercise does not require you to use the THIS pointer, however feel free to do so if you wish.

5. Extending the Complex Number Class – More Operator Overloading

Add three new member functions to the complex class (of Day 5), by overloading the “<”, “>” and “++” prefix operators. The “<” and “>” operators are overloaded by testing whether the norm of one complex number is less than or greater than the other, respectively. The “++” prefix operator is overloaded, by adding 1 in the usual way. Here you should definitely use the THIS pointer as done in this chapter.

Test the new class by writing a main function that defines two complex numbers, prints the number with the larger norm, adds 1 to each of the complex numbers and then prints the one with the larger norm after the addition.

6. Using the APSTRING class

Write a program that reads in a string and determines whether or not it is a palindrome (i.e. whether or not it reads the same backwards and forwards). This uses indexing ([]) and length.

7. Using the APSTRING class (*)

Write a program that reads in a string and prints a table of how many times each character a-z appears. You should ignore any non-alphabetic characters, but you should consider capital letters the same as non-capital. This uses find, length and substr.

Longer Exercises

1. A Class for Large Integers Using Strings - A Class in a Class (*)

Since most computers have a limit on the size of an integer, in order to do exact arithmetic on very large integers without overflow errors, it is necessary to create our own data type.

The class should allow the definition of large integers (using constructors). The class should allow us to add, multiply, print, and compare them. There are many ways to implement a class for large integers, but here we will use strings.

The private data should include a string and a length. For example the number 345216789, would be stored in two fields: a string of characters “345216789” and an integer 9 representing its length.

(Note that since the string class has a public length function, the inclusion of the length field here is a question of style. Would we rather call the string length function every time we need that information, or just call it once in the constructor, and reference the private field from then on? Since we will use the length of the number/string a lot in the implementation of the member functions, we chose to put it in explicitly. Note that we made the opposite choice in the next long exercise because the length function is not used as often in the implementation of the member functions.)

The constructors should include:

i. A no argument default constructor that initializes the number to 0.

ii. A one argument constructor that takes a regular integer and initializes the object to it.

iii. A one argument constructor that takes a string and initializes the number to that string.

The second constructor needs a little thought. We will need to construct the Largeint digit by digit from right to left. The next digit from the regular integer x can be retrieved with x%10, and x can be set to x/10 for the next iteration. This digit can be placed into the string for the Largeint by using the overloaded “+” operator in APSTRING for left concatenation of a character and a string.

The member functions should include overloading the “+”, “*”, “<”, “>”, “==” and “<” operators in the natural way. It is helpful to use functions from the APSTRING class to make the implementation of these as easy as possible. Of course, these functions can also use each other. For example, it makes sense for the overloaded * to make repeated use of the overloaded +.

Puzzle: How many 0’s appear at the end of 100! (100 factorial)?

Try to answer this puzzle analytically, then write a program using the new class to check your answer. The digits of 100! (not including the number of zeros at the end is shown below:

100! = 933262154439441526816992388562667004907159682643816214685929638952

175999932299156089414639761565182862536979208272237582511852109168640…0

Notes and Hints for the Add and Multiply Member Functions:

There are many algorithms one can use to add or multiply integers. I will suggest some intuitive methods based on the ones most people use to do arithmetic with pen and paper.

We will look at addition first since multiplication will use addition. We add the long integers right to left just as we do with pen and paper.

Addition:

We start with a portion of the class definition stored in Largint.h.

Class Largint

Private: apstring str;

Int length;

Public: Largint();

Largint(int);

Largint(apstring);

Largint & operator + (const largint &) const;

// This overloads the + operation for adding two Largints.

Largint & operator + (const int &) const;

// This overloads the + operation for adding an int to a Largint.

…

Here is a portion of the implementation for the overloaded + member functions as it would appear in LargInt.cpp, along with comments explaining the ideas.

Largint Largint :: operator + (const Largint &a) const

{

int i1 = a.length-1;int i2 = length-1; // Start both Largints at their right ends

int carry = 0; // Stores the carry for the next column’s addition

apstring n; // Used to store the addition

int total;// Used to calculate the result of the addition in each column

while ((i1 >= 0) & (i2 >= 0))

// continue adding column by column as long as there are digits in both Largints.

{

total = (a.str)[i1] + str[i2] + carry – ‘0’ – ‘0’;

// This adds the two ascii characters in the corresponding columns of both strings,

// and adds in the carry bit. The ascii values for ‘0’ are subtracted twice so as to get the

// real integer result.

if (total>9) carry =1 else carry = 0; // Recalculate the carry bit

n = (total%10 + ‘0’) + n;

// Takes the result of this column’s addition (total%10), converts it to ascii by adding ‘0’,

// and concatenates it to the left end of the running calculation. Note that the second + is

// overloaded for concatenation between a character and an apstring.

i1--; i2--// Move to next left digit of each number

}

// Here you need to add code to handle what happens after one of the Largints runs out of

// digits. If i1 and i2 are negative, then you must concatenate the final carry to the left

// end of the apstring n. If only one of i1 and i2 are negative, then the details depend on

// whether or not the carry is zero or one. If the carry is zero, then the remainder

// of the longer Largint is concatenated on the left end of the apstring n. This can

// be done using the overloaded + for apstring and the member substr function.

// The details in the case when the carry is one are left to you.

…

Largint result = n;

return result;

// We return a Largint equal to the final string n.

To overload the + operator for adding an int to a Largint, we can use the “this” pointer with a simple call to the overloaded + for adding two Largints.

Largint Largint :: operator + (const int &i) const

{

Largint a = i;

return (*this) + a;

}

Multiplication:

There are many ways to accomplish multiplication. Here is a sketch of an algorithm based on the method most of use with pen and paper. It computes partial sums and adds them all together. We call one number the multiplier and the other, the multiplicand. Multiply the rightmost digit of the multiplier by the multiplicand and store the result in total. Move left in the multiplier, and multiply the next digit of the multiplier by the multiplicand, padding the result on the right with one zero before adding it to our total. This continues, but each time we move left, we pad the result with one extra zero, before we add it to the total. When the multiplier runs out of digits, we return the total.

Multiplying the multiplicand by a single digit x of the multiplier can be done with a loop from 1 to x that adds the multiplicand to repeatedly. These additions, as well as the additions of the partial sums to the total, should be done using the overloaded + operator.

Note that the simpler method of multiplying two Largints y and z, by adding y to a running total, z times, is much too inefficient. It would use approximately z additions, while our method would use at most 10 log z additions.

Advanced Features - Subtraction:

We did not include subtraction in this class, but it is certainly a natural choice for a member function. One could write a subtraction function from scratch. However, it is a nice exercise to build subtraction out of addition, as it is done in the ALU hardware. When engineers design an ALU (Arithmetic and Logic Unit), they assume that the numbers are represented as binary two’s complement, and they implement subtraction by a combination of complement and addition. If you don’t know anything about ALUs or two’s complement numbers, then you can learn a little about it from the discussion below which assumes base ten.

The “complement” of an n-digit (base ten)number is the difference between that number and 10n. We subtract an n-digit number A from an n-digit number B, in two steps:

  1. Find the “complement” of A.
  2. Add it to B.
  3. Return the rightmost n-digits in the answer.

For example: To subtract 34 from 89, we calculate the complement of 34 which is 66, and add it to 89. This gives 155. If we ignore the leading 1 and return the two rightmost digits, then we see the correct result, 55. The reason this works is because we are effectively computing 10n-A+Band then subtracting 10n, which equals B-A.

The only thing left to do is explain how to calculate the complement of a base 10 number without doing any subtraction. This can be done by replacing each digit x in the number by 9-x, (including the implicit leading zeros, if any), and then add 1 to the final result. For example: To subtract 34 from 267, we take the complement of 034 (note the leading zero). This is done digit by digit. The 0 is replaced by 9, the 3 with 6, and the 4 with 5. This gives 965. Then we add 1 which gives 966. This is added to 267 giving 1233. Ignoring the leading 1, gives 233 as the final result.

A new private function called complement shouldbe defined, andthe public overloaded + should be called. The leading 1 can be deleted using an appropriate APSTRING function.

2. A Class for Sets Using Strings - Another Class in a Class

There are some very efficient and clever ways to implement sets using bits and bitwise operations, but here we concentrate on getting more experience with the APSTRING class.

Recall that a set is an unordered collection of unique things, so that there should be no duplicates in a set, nor should there be any access to an ordering of the elements. For simplicity we will consider a class to represent a set of alpha-numreric characters, (i.e. a-z, A-Z and 0-9). The class should be able to calculate the union, intersection or difference of two sets of characters, the number of elements in the set, whether or not a set is empty, whether or not one set is a subset of another, and whether or not a given character is a member of a set.

We will implement the class using strings. The private members should include:

  1. A string of characters. There is no need to keep the characters sorted.
  2. A function that takes a string and compresses it so that there are no duplicates. This private function will be very useful in the implementation of the public member functions. The client for our class will have no use for this function, hence we make it private.

There should be three constructors:

  1. A no argument constructor that initializes the set to empty.
  2. A one argument constructor of type string that initializes the set to the characters in the string.
  3. A one argument constructor of type integer that initializes the set to the digits in the integer.

The public member functions should include:

  1. MemberOf – This takes a char and returns a Boolean value indicating whether or not the char is a member of the object set. This can be done by searching with the appropriate APSTRING function.
  2. Complement – This has no parameters. It should be implemented by overloading the unary “-“ operator. The complement of S can be computed as follows. Let U bethe “universal” set consisting of all alphanumeric characters. For each character in S, delete that character from U. Return U.
  3. Union – This takes a set S and returns a set equal to the union of the object with S. This should be implemented by overloading the + operator, and using the private function to remove duplicates.
  4. Intersection – This takes a set S and returns a set equal to the intersection of the object with S. This should be implemented by overloading the * operator. Since A*B = -(-A+-B), this can be implemented by calling union and complement.
  5. Difference – This takes a set S and returns a set equal to the characters in the object which are not also in S. This should be implemented by overloading the – operator. Since A-B = A* -B, this can be implemented by calling intersection and complement.
  6. Size – This has no parameters. It returns the number of characters in the object set.
  7. Empty – This has no parameters. It returns a Boolean value indicating whether or not the set is empty. It can be implemented by a call to size.
  8. SubsetOf – This takes a set S and returns a Boolean value indicating if S is a subset of the object set. This should be implemented by overloading the “<=” operator. Since A <= B if and only if B-A is not empty, it can be implemented by a call to difference and empty.
  9. Print – This prints out a set. It should be implemented by overloading the < operator.

Write a program using the set class that reads in the scores of 10 quizzes for each of 30 students. The scores on each quiz are integers in the range 0-9. The program should determine:

i. Which grades if any appeared on each of the thirty students’ lists.

ii. Who if anyone received a different grade on each quiz.

iii. What grades if any appeared on nobody’s list.

iv. Who if anyone received the same score all the quizzes.