HW: String Calculator

HW: String Calculator
Overview
Bjarne Stroustrup (the inventor of C++ and former Texas A&M Professor) is jealous of Python’s support for
arithmetic with unbounded integers. Help Bjarne to feel better about C++ by building a calculator to do basic
arithmetic operations with arbitrarily large numbers represented internally as strings, i.e., sequences of
characters.
For this assignment, you will need to implement addition (same signs only) and multiplication using strings.
The starter code from Canvas will provide a framework with comments in main.cpp and
string_calculator.cpp where you will implement your code.
Example Run of the Calculator
String Calculator
"q" or "quit" or ctrl+d to exit
>> 1371195958099968000 * 191898783962510625
ans =
 263130836933693530167218012160000000
>> 8222838654177922817725562880000000 + 263130836933693530167218012160000000
ans =
 271353675587871452984943575040000000
>> quit
Farvel!
Objectives
1. Use C++ string objects.
2. Use a built in C++ class.
3. Implement standard arithmetic algorithms
Getting Started
1. Get starter code.
2. Read the String Calculator Requirements below
3. Review below the Recommendations for basic tips and the Appendix for more guidance.
a. Will make homework much easier.
b. Best advice is get started early.
Starter Code
The starter code contains three files (submit these to the autograder):
1. main.cpp: contains the user interface that drives the program (TODO).
2. string_calculator.h: contains required function declarations (read).
3. string_calculator.cpp: contains function definitions (TODO).
Requirements (100 points)
String Calculator Functions
1. unsigned int digit_to_decimal(char digit)
digit_to_decimal(‘7’) should return 7
digit_to_decimal('/') should throw std::invalid_argument
2. char decimal_to_digit(unsigned int decimal)
decimal_to_digit(7) should return ‘7’
decimal_to_digit(36) should throw std::invalid_argument
3. std::string trim_leading_zeros(std::string num) // positive only
trim_leading_zeros(“00123”) should return “123”
trim_leading_zeros(“0000123”) should return “123”
4. std::string add(std::string lhs, std::string rhs) // two positives only
add(“1”, “2”) should return “3”
add(“19”, “2”) should return “21”
5. std::string multiply(std::string lhs, std::string rhs) // two positives only
multiply(“2”, “3”) should return “6”
multiply(“24”, “2”) should return “48”
Allowed Includes
1. iostream
2. limits
3. sstream
4. string
5. String_calculator.h
Compilation
The program must compile without warnings or errors. The program should also handle exceptions and avoid
runtime errors.
g++ -std=c++17 -Wall -Wextra -pedantic -Weffc++ string_calculator.cpp main.cpp
User Interface
Main program should prompt for input and perform calculations. Below is a sample run. Sser input is in bold
red; everything else is output. ⎵ is a space character (‘ ’). ↵ is a newline character (‘\n’, also
displayed as ) ⮒ . Formatting must be followed exactly.
$ ./a.out ⎵
String Calculator↵ ⎵
"q" or "quit" or ctrl+d to exit↵ ⎵ ⎵ ⎵ ⎵ ⎵ ⎵
>>⎵1 + 1↵ ⎵ ⎵
↵
ans =↵ ⎵
↵
⎵⎵⎵⎵2↵
↵
>>⎵quit↵
↵
farvel!↵
↵
Recommendations
1. Start early.
2. Download the starter code.
3. Read the header file.
4. Compile and run the program on your computer.
A. It won’t do anything, but it also won’t crash
5. Pick a function to implement first.
A. Recommendations: decimal_to_digit, digit_to_decimal,
trim_leading_zeros (small, positive)
B. Plan your program on paper (digital or analog) before mashing the keyboard
C. Implement only simple functionality at first; you can add more later
6. Recompile and rerun.
A. Check for errors.
B. If no errors, move on
C. Else, start debugging
7. Once you have some functionality, submit to Gradescope.
A. Ensure formatting matches the expected output (spaces, newlines, “>>”).
B. If the basic tests for that function pass, move on
C. Else, start debugging
8. Continue by picking new tests and writing just enough code to pass them, adding more
functionality each time (step 5)
9. See the Appendix below if you’d like additional guidance.
Make your Code Easy to Understand
1. Use descriptive (long) naming conventions for variables and functions.
2. Add comments to the code to describe anything which is not obvious from the code.
3. Use whitespace (indentation, newlines) to visually organize code.
4. Use functions to reduce code duplication and increase abstraction.
Conventions like meaningful variable names and commenting will make it easier for you to understand your
own code and implement your algorithms!
Extra Challenges (10 points)
While you only need to do the requirements for full credit (100 pts), there are several extra challenges you can
do for bonus points. Bonus points above 100 will be treated as extra credit that can benefit your other
homeworks. There are 10 bonus points available.
Implement negative numbers (5 points):
Extend your “add” and “multiply” functions to handle negative numbers. The “add” function can assume both
operands are negative or both are positive. The “multiply” should work with any combination of negative and
positive operands. This will require “trim_leading_zeroes” to work with negative numbers as well.
trim_leading_zeros(“-00123”) should return “-123”
add(“-1”, “-2”) should return “-3”
multiply(“2”, “-3”) should return “-6”
multiply(“-2”, “3”) should return “-6”
multiply(“-2”, “-3”) should return “6”
Implement subtraction (2.8 points):
Create a function “subtract” with the following declaration and operation:
std::string subtract(std::string lhs, std::string rhs)
subtract(“1”, “2”) should return “-1”
subtract(“1”, “-2”) should return “3”
subtract(“-1”, “2”) should return “-3”
subtract(“-1”, “-2”) should return “1”
Note that your “subtract” function will essentially implement opposite-sign addition, so you can enhance your
“add" function to support different signs by calling “subtract”. Likewise, you can implement part of “subtract”
just by calling the “add” function! (when the signs are correct)
Support operations in all bases from 2 to 36 (1.1 points):
>> c86ipn83stajn52_30 + 8hmas0ct_30
ans =
 c86ipn8cgllhni1_30
Hexadecimal examples:
>> dead_16 + c0de_16
ans =
 19f8b_16
Improved I/O Handling (1.1 points):
Remember the Answer and Allow Single Values and Empty Lines
>> 2 * 3
ans =
 6
>> ans + 10
ans =
 16
>> 123
ans =
 123
>>
>>
Perform input validation and Implement quit on EOF (ctrl+D)
>> x + y
Invalid LHS
>> 6 + x
Invalid RHS
>> <ctrl+D>
farvel!
Appendix: Suggestions for the String Calculator
5-Minute Video Overview
If you prefer, you can see a discussion of this material in a short video on Youtube:
● 5-minute Video: Getting Started with String Calculator
The Problem-Solving Mindset
As with all homework assignments, the goal of String Calculator is to help you develop critical problem solving
skills through applied programming experience. But you don’t have to be a master programmer to start
thinking like one!
At the root of each problem is a simple question: “What set of steps (or, algorithm) do I need to make this
happen?” Oftentimes, a good place to start is with steps you naturally use when doing the problem yourself.
For example, in Mountains and Valleys, you had to determine if a sequence of digits represented a mountain or
valley range based on direction changes. If you were given a number hundreds of digits long and asked to
check if it were a mountain or valley range, what would you do? You would probably start checking digit-bydigit for direction changes. That is essentially the number slicing technique we recommended!
It’s also the reason we discouraged solutions that were hard-coded for 3 or 4 digits. As humans, we might
make simplifications like that, but you will find thinking at a large scale (e.g., hundreds of digits) can help you
more clearly recognize the steps on a small scale (e.g., just three digits) and put you in a better mindset for
developing algorithms.
In this homework, you will be forced to think at scale because we are working with strings, some of which will
be very long. You need to implement algorithms that can iterate through strings of any size and apply the
appropriate operations. So what to do?
Let’s consider how you might tackle this problem on your own before thinking about the code. Note: this is not
a new technique. Recall that we talked about the simple software development process: Analyze → Design
→ Implement. All we are doing here is to analyze the problem by thinking through the steps you might want
to perform. From there, you can sketch out your design before beginning implementation details.
Long Addition
It’s probably been some time since you sat down and performed an addition problem by hand, but the same
steps still apply. When you perform long addition, you stack the numbers, add column-by-column, and carry
forward a digit when the sum is 10 or more.
For example, let’s add the numbers 47349 and 6232:
 1 1 ← Carry
 4 7 3 4 9
 + 6 2 3 2
 -----------
Result: 5 3 5 8 1
If we look at each individual step, we can see that we need only to traverse the two operands from right-to-left,
adding as we go. We’ll need something to store the carry, and a place to store the result.
Now that we have the general idea, translating to code is a matter of identifying the variables and mechanisms
needed to do these steps. Think about data types, loops, and the conditional logic you might need at each
step. If you have to write down the actions in more detail to get a better understanding, go for it!
If you want more practice, CalculatorSoup provides an excellent Online Long Addition Calculator which breaks
down the steps for any operands you provide.
Long Multiplication
At first, multiplication might sound more difficult than addition, but it will be much the same in that you are still
going to iterate over the operands digit-by-digit and apply the operation (in this case, multiply). The main
difference in long multiplication is the inclusion of partial products.
Let’s consider the product of 4512 and 28. We start by computing the partial product for the 1’s digit. Note
that at each step, we’re just multiplying the 1’s digit of the lower number, 8, with each digit of the upper
number, and adding the carry.
 3 4 1 ← Carry for the 1’s digit: 8
 4 5 1 2
 * 2 8
 -----------
 3 6 0 9 6 ← Partial Product for the 1’s digit: 8
Next, we’ll repeat the operation for the 10’s digit, 2:
 1 ← Carry for the 10’s digit: 2
 4 5 1 2
 * 2 8
 -----------
 3 6 0 9 6 ← Partial Product for the 1’s digit: 8
 9 0 2 4 0 ← Partial Product for the 10’s digit: 2
By this point, we’ve uncovered a couple of special considerations:
1. It’s evident that we are doing two levels of iteration, so we might need more than just a single loop to:
1. multiply a digit in the bottom number by each digit of the top number and
2. traverse all digits in the bottom number.
2. With each new digit of the bottom number, we have to account for its order (1’s, 10’s, etc.) by placing the
correct number of zeros at the right.
We’re basically at the end of the calculation. All that remains is to add the partial products, but we already have
an add function!
 3 6 0 9 6
 + 9 0 2 4 0
 -----------
Result: 1 2 6 3 3 6
By leveraging the addition function that is already complete, we can sum the partial products as we go,
simplifying the multiplication function greatly.
Again, CalculatorSoup has a helpful Online Long Multiplication Calculator with these steps and visualizations.
Handling the Signs
For 5 bonus points, you can extend your program to handle negative numbers as well.
In multiplication, you only need to check if signs are the same (result is positive) or different (result is
negative). In addition, we will only test same-sign numbers in the base requirements. If both are positive, the
result is positive, and if both are negative, the result is negative.
The algorithms themselves are the same. You will just need to check if the number begins with ‘-’ to determine
negative or not, and remember it to update the final result.
Next Steps
These examples demonstrate one set of operations for adding and multiplying a digit at a time. There are
many alternatives; for instance, look up Left-to-Right Addition.
You may have your own idea for a novel algorithm to do the task. Pursue it! Implementing your ideas is a
great way to develop your problem solving skills. If you want an additional challenge, consider writing the
subtraction algorithm. Not only can you earn bonus points, but you can make a more full-featured calculator.
Remember, there is a lot to do! Whatever approach you take, you want to get started as soon as possible
because it will take a long time just to write the code for these operations.