As you may already know from earlier courses, integer
values in C++ (as well as other programming languages) are limited by the number of bits used to
represent these data. For instance, a 64-bit unsigned
integer has the
maximum value of 2^64 - 1 or 18446744073709551615.
To represent integers of arbitrary length, we can use a linked list data structure such that that a node in the linked list corresponds to a single digit in the integer.
For instance, the number 123 can be stored as linked-list that could look like
this:
[ 3 ] -> [ 2 ] -> [ 1 ] -> NULL
Note that the first (or head) node in this list contains the least
significant digit (in this case 3), while the last node contains the most
significant digit (1).
For this problem, you are to read in pairs of arbitrary length integers into custom, user-defined linked lists in C++ (see Requirements below), use the lists to add each pair of numbers, and produce correct output as outlined below.
Note, this problem is inspired by Problem 8.19 from Elements of Programming Interviews and Problem 2.5 from Cracking the Code Interview.
The goal is to cover an interview-related practice problem based on a basic data structure (container) from CS140, but with a more C++/OOP-centric view, namely using classes, templating, and passing by reference/value. Using friendship and/or operator overloading is optional.
It will be very likely more work than the average Challenge given these C++-oriented objectives/pointer requirements so please start early!
You will be given a series of integers from standard input in the follow format:
integer1 integer2 integer1 integer2 ... integer1 integer2
Each integer is of arbitrary length. Moreover, integer1 is not
guaranteed to be the same length as integer2.
You are to add each pair of integers. Given the following input:
1 1 123 123 1 12
Your program should output the following:
2 246 13
On top of being interview prep, this specific assignment is intended to both review and assess your understanding of a templated sequence container (linked list) from a programming perspective (vs. the more academic perspective from your Reading). Thus, to accomplish this learning objective, your solution is required to do the following:
You must create a custom, templated linked list implementation in C++ (i.e., you cannot use std::list); however, you are allowed to use Dr. Emrich's code and/or your notes from class as a starter/template.
In your main function (or equivalent) you must instantiate your list with the fundamental type int.
You must define a function that takes two lists and returns a list that contains the sum of the two input lists. This can be a simple global function, i.e, it is not required to overload either "+" or "+=" (but of course you could; this would be more natural in syntax). It is also up to you whether the function(s) are defined as "friends" or not.
You must manage dynamic memory properly for full credit (i.e., no memory leaks or segmentation faults).
You may wish to read the integers in as std::strings.
Be sure to account for the carry when you perform addition.
We will grade your submission relative to the rubric below.
Note that failure to use a custom, templated list results in a maximum grade of 24/30 (C+)
+2 Code is well formatted, commented (inc. name, assignment, and overview), with reasonable variable names +6 uses custom, templated list with fundamental type int +1 defines a function that takes two lists and returns the sum +3 No issues reported by valgrind on second test applied +18 Test cases involving at least one number with two or more digits successfully solved (2 points each)
To faciliate testing, you were previously asked to clone the course Github repository as follows:
git clone https://github.com/semrich/ds302_19.git cs302
For this assignment, update this clone by using the following:
git pull
We'll discuss this in class but note that your program must be named "solution.cpp" and compilable using make. To test your solution against ours, type:
make test
To submit your solution, you must submit a single archive (.zip, .tar, .gz, etc.) on Canvas prior to the deadline.
Note: Although submission will be faciliated by Canvas, we will compile and test on EECS lab machines!
If you develop your solution elsewhere please make sure it works on the lab computers prior to the deadline