Add two digit strings and return the result as string

Question

I haven't done C in a while. This looks like a simple problem to start.

Leetcode problem 415

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
...
Note: [1. ... 2. ... 3. ... ] 4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

It is working but I would like the comment on the style and being proper C code.

char * addStrings(char * num1, char * num2){
 int len1 = strlen(num1);
 int len2 = strlen(num2);
 int result_len = len1 > len2? len1: len2;
 result_len += 1;
 char *result = malloc(result_len+1);
 char *p1 = num1 + len1-1;
 char *p2 = num2 + len2-1;
 char *rp = result + result_len;
 *rp = '0円';
 rp--;
 int carry = 0;
 char zero='0';
 int digit;
 int d1;
 int d2;
 while (len1 || len2) {
 if (len1) {
 d1 = (*p1)-zero;
 p1--;
 len1--;
 } 
 if (len2) {
 d2 = (*p2)-zero;
 p2--;
 len2--;
 }
 int tmp = d1 + d2 + carry;
 digit = tmp % 10;
 carry = tmp / 10;
 *rp = digit+zero;
 rp--;
 d1 = 0;
 d2 = 0;
 }
 if (carry) {
 *rp = carry+zero;
 } else {
 rp++;
 }
 return rp;
}

Answer 1

Always Initialize Variables

There is one possible bug in the code, the variables d1 and d2 assume that both num1 and num2 have values, this may not be true. The C programming language does not initialize variables by default like some other languages, especially local variables. All of the variables should be initialized before the loop.

This also creates multiple paths through the code if either num1 or num2 do not have a value and error checking is added.

char * addStrings(char * num1, char * num2){
 int len1 = strlen(num1);
 int len2 = strlen(num2);
 if (!len1 && !len2)
 {
 fprintf(stderr, "Neither string has an integer value.");
 return "0";
 }
 else
 {
 if (!len1)
 {
 return num2;
 }
 if (!len2)
 {
 return num1;
 }
 }
 ...
 return rp;
}

Complexity

With the added error check the function addStrings() is too complex (does too much). As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

Probably the best thing to do here is to break addStrings() into 2 functions, one that does the error checking, and one that calculates the value of the string. The addStrings() function should do the error checking itself, and then call a function to calculate the value of the string.

Missing Headers

In addition to the missing header files noted by vnp an include of the header file string.h is necessary to allow strlen() to compile, at least on my computer with my C compiler (Windows 10, Visual Studio 2019).

DRY Code

There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code multiple times it is better to encapsulate it in a function. If it is possible to loop through the code that can reduce repetition as well.

This code is repetitive and the manipulation of the pointers and counters isn't necessary at this point.

 if (len1) {
 d1 = (*p1)-zero;
 p1--;
 len1--;
 } 
 if (len2) {
 d2 = (*p2)-zero;
 p2--;
 len2--;
 }

It might be better to just check if pN has a value and use what it points to if it does, change the pointers and the counters at the end of the loop.

 if (p1) {
 d1 = (*p1) - zero;
 }
 if (p2) {
 d2 = (*p2) - zero;
 }

Scope of Variables

The integer variables digit, d1 and d2 are never used outside the loop so they can be declared within the loop itself. Only declare the variables when they are needed.

In Summation

As noted by vnp there is a memory leak.

An example of what how I would write the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static const unsigned char zero = '0';
char addCharacters(char *p1, char *p2, int *carry)
{
 int digit = 0;
 int d1 = 0;
 int d2 = 0;
 if (p1) {
 d1 = (*p1) - zero;
 }
 if (p2) {
 d2 = (*p2) - zero;
 }
 int tmp = d1 + d2 + *carry;
 digit = tmp % 10;
 *carry = tmp / 10;
 return digit + zero;
}
char* calculateStringValue(char *result, char num1[], int len1, char num2[], int len2, int result_len)
{
 char *rp = result + result_len;
 *rp = '0円';
 rp--;
 int carry = 0;
 char *p1 = num1 + len1-1;
 char *p2 = num2 + len2-1;
 while (len1 || len2)
 {
 *rp = addCharacters(p1, p2, &carry);
 --len1;
 --len2;
 p1 = (len1 > 0) ? --p1 : NULL;
 p2 = (len2 > 0) ? --p2 : NULL;
 --rp;
 }
 if (carry) {
 *rp = carry + zero;
 } else {
 rp++;
 }
 return rp;
}
char * addStrings(char * num1, char * num2){
 int len1 = strlen(num1);
 int len2 = strlen(num2);
 if (!len1 && !len2)
 {
 fprintf(stderr, "Neither string has an integer value.");
 return "0";
 }
 else
 {
 if (!len1)
 {
 return num2;
 }
 if (!len2)
 {
 return num1;
 }
 }
 int result_len = len1 > len2? len1: len2;
 result_len += 1; // allow for carry.
 char *result = malloc(result_len + 1);
 if (result == NULL)
 {
 fprintf(stderr, "malloc failed in addStrings\n");
 return NULL;
 }
 return calculateStringValue(result, num1, len1, num2, len2, result_len);
}
int main() {
 char num1[] = "2048";
 char num2[] = "9999";
 printf("AddStrings returns %s\n", addStrings(num1, num2));
 return 0;
}

• wispymisty: This is great. Thanks a lot ! I will try to write something close to your example on my own. In my haste, the original code was straight from my Leetcode's online answer area. So there is no main or library. I will post full code with main and headers in the future.
• G. Sliepen: You can also see here why you would want to store numbers in little-endian order: it avoids having to read backwards. Also if either num1 or num2 is allowed to be "", and be treated as "0", then why not allow both num1 and num2 to be "" and cause the result to be "0"?
• pacmaninbw: @G.Sliepen I could, but it isn't specified in the question.

Answer 2

• The caller cannot free the result: if the loop completes without carry, the pointer returned is not the pointer allocated. Memory leaks.

• Missing #include <stdlib.h> and #include <string.h>.

• wispymisty: Yes. Need another copy for final result and free the current one. I will update it.

Answer 3

Very long strings

String length is not limited to INT_MAX. Better to use size_t

// int len1 = strlen(num1);
size_t len1 = strlen(num1);

const

As code does not alter data pointed to by num1, num2, use const. This allows code to be called with const strings, add info for a user to know the strings are not changed and provides easier to find compiler optimizations.

// addStrings(char * num1, char * num2){
addStrings(const char * num1, const char * num2){

Error check

As code is attempting to handle arbitrary long numbers, a failed allocation is even more likely. Add a check.

char *result = malloc(result_len+1);
if (result == NULL) {
 // maybe a message on stderr?
 return NULL;
}

Pedantic code would also check for addition overflow.

size_t len1 = strlen(num1);
size_t len2 = strlen(num2);
if (SIZE_MAX - len1 <= len2) {
 return NULL;
}

zero vs. '0'

Code promotes sub-int operands to int before subtraction. Might as well use an int zero.

Subtracting '0' is idiomatic. Recommend:

//char zero='0';
// d1 = (*p1)-zero;
 d1 = *p - '0';

Code should return the allocated pointer

UB with empty string

Corner concern:

char *p1 = num1 + len1-1;
// same as 
char *p1 = num1 - 1; //UB

Sample

Note: untested

char* addStrings(const char *num1, const char *num2) {
 size_t len1 = strlen(num1);
 size_t len2 = strlen(num2);
 if (len1 >= SIZE_MAX - 1 - len2) {
 return NULL;
 }
 size_t len_max = len1 > len2 ? len1 : len2;
 size_t len_min = len1 < len2 ? len1 : len2;
 char *result = malloc(len_max + 2); // +1 for carry, +1 for 0円
 if (result == NULL) {
 return NULL;
 }
 char rp = result + len_max + 1;
 *rp = '0円';
 char *p1 = num1 + len1;
 char *p2 = num2 + len2;
 int acc = 0;
 len1 -= len_min;
 len2 -= len_min;
 while (len_min-- > 0) {
 acc += *--p1 - '0' + *--p2 - '0';
 *--rp = acc % 10 + '0';
 acc /= 10;
 }
 while (len1-- > 0) {
 acc += *--p1 - '0';
 *--rp = acc % 10 + '0';
 acc /= 10;
 }
 while (len2-- > 0) {
 acc += *--p2 - '0';
 *--rp = acc % 10 + '0';
 acc /= 10;
 }
 if (acc) {
 *--rp = acc % 10 + '0';
 } else {
 memmove(rp - 1, rp, len_max + 1);
 rp--;
 }
 return rp;
}

• wispymisty: Thanks. It looks like I have been writing code with wreckless abandon.
• chux: @wispymisty We all LSNED.