Challenge 02: Adding List-Based Integers

Problem

As you may already know from Fundamentals or Computer Architecture, integer values in C and C++ are limited by the number of bits used to represent that 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 singly 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 looks like the following:

[ 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 singly linked lists, then use the lists to add the two numbers, and finally output the results.

Input

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.

Output

You are to add each pair of integers and then output the resulting total as a single number:

result1
result2
...
resultN

Example

Given the following input:

1 1
123 123
1 12

Your program should output the following:

2
246
13

Requirements

Your solution must meet the following requirements:

1. You must create a custom linked list (ie. you cannot use std::list).

2. Your linked list must be templated.

3. If you dynamically allocate memory, then you must be sure you manage it properly (ie. no memory leaks or segmentation faults).

Hints

1. You may wish to read the integers in as std::strings.

2. You may wish to define a struct Node.

3. You may wish to define a struct List with an operation to add an item to the list.

4. You may wish to define a function that takes two lists and returns a list that contains the sum of the two input lists.

5. Be sure to account for the carry when you perform addition.

Preparation

Before working on this problem, you should use git to pull the changes from the upstream assignments repository:

# Go to your repository
$ cd path/to/repo

# Make sure we are on master branch
$ git checkout master

# Add upstream remote repository
$ git remote add upstream https://gitlab.com/nd-cse-30331-fa16/assignments.git

# Fetch and merge upstream changes into local repository
$ git pull upstream master
From gitlab.com:nd-cse-30331-fa16/assignments
  * branch            master     -> FETCH_HEAD
Merge made by the 'recursive' strategy.
  challenge02/Makefile     | 26 ++++++++++++++++++++++++++
  challenge02/input        | 11 +++++++++++
  challenge02/output       | 11 +++++++++++
  challenge02/solution.cpp |  9 +++++++++
    4 files changed, 57 insertions(+)
  create mode 100644 challenge02/Makefile
  create mode 100644 challenge02/input
  create mode 100644 challenge02/output
  create mode 100644 challenge02/solution.cpp

When you perform the git pull you may be asked to write a commit message. You can simply use the default message by closing the text editor it brings up.

Once this is complete, you should have the Makefile, input, output, and solution.cpp for this challenge.

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Challenge 02 - TA assignment list.

$ cd path/to/repo                   # Go to your repository
$ git checkout master               # Make sure we are on master branch
$ git pull                          # Make sure we have changes for GitLab
$ git checkout -b challenge02       # Create challenge02 branch
...                                 # Do your work
$ git commit                        # Commit your work (can do this multiple times)
$ git push -u origin challenge02    # Push branch to GitLab