$30
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-by-digit 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.