8.2.7. cpalnumber.cpp

The introduction to the palindrome-number problem outlined an overall solution, and designed two algorithms for identifying general palindromes. The examples in this section implement two C-string-based programs that follow the outline and implement the designed palindrome algorithms. Generating and squaring candidate numbers are inherently arithmetic operations. Although it is possible to isolate and examine the individual digits in a number (as illustrated in a subsequent example), it is both easier and in line with the subject of the current chapter to convert the number to a string, allowing the program to use string functions to validate the puzzle's requirements.

The algorithms rely on and develop two additional functions: itoa and reverse. When designing algorithms, developers often encounter sub-problems that, independent of the problem's complexity, they logically treat as a single, atomic step. This approach simplifies the design, reading, understanding, and programming of algorithms. We can choose to visualize function calls as a single operation or as a gateway to a set of complex statements.

Identifying C-String Palindromes With The Finger Method

The first solution converts the squared candidate number to a C-string with some variant of the "ASCII to integer" function: atoi. The ANSI standard doesn't require this function, so the example creates one following the initial puzzle solution. Once the solution squares the candidate number, it converts it to a C-string. This solution calculates index values for the left- and right-hand fingers to select characters for comparison.

#define _CRT_SECURE_NO_WARNINGS						// Microsoft only
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
	for (int number = 1; ; number++)				// (a/I.i and I.ii)
	{
		int	square = number * number;			// (b/II)

		//----------------------------------------------	   III
		char	s[100];						// (c)
		_itoa(square, s, 10);					// (d)
		//_itoa_s(square, s, 100, 10);				// (e)

		//----------------------------------------------	   IV - begin case analysis
		if (strlen(s) < 6)					// (f/IV.i)
			continue;

		if (s[0] == '0' || s[strlen(s) - 1] == '0')		// (g/IV.ii)
			continue;

		//----------------------------------------------	   IV.iii - palindrome detection
		int	i;						// (h)
		for (i = 0; i < strlen(s) / 2; i++)			// (i)
			if (s[i] != s[strlen(s) - 1 - i])		// (j)
				break;

		if (i == strlen(s) / 2)					// (k)
		{
			cout << number << " " << square << endl;
			break;
		}
	}

	return 0;
}

Converting Numbers To C-Strings

Typecasting works well when the original and converted datatypes are similar. For example, a program can cast one integer type to another, or one floating-point type to another, but it can't cast a number to a string. When available, the itoa function can perform the conversion. Although various versions are readily available on the Internet, creating a simple version offers valuable insight into a common task. Given an integer, convert it into a string that looks like the number. The function can process the digits in the number from left to right or right to left. Each approach offers advantages and disadvantages, but both must isolate each digit and convert it into an ASCII character. This task is more abstract and less familiar than detecting a palindrome, so the examples present their solutions with little introduction but with detailed explanations.

char* itoa(int n, char* s)				// convert n to a string, store it in s
{
	bool	sign = n < 0;				// capture the sign if n is negative
	char	temp[100];				// stores chars in reverse order
	int	index = 0;				// index into temp

	if (sign)					// captures the sign if n is negative
		n = -n;					// make n positive for processing

	// converts the number to characters right to left - the function's heart
	do
	{
		temp[index++] = (char)(n % 10 + '0');	// isolates and converts the rightmost digit
		n /= 10;				// discards lowest (right-most) digit
	} while (n);					// ends when n is 0

	// prepares the output
	int i = 0;					// processing index into s
	if (sign) s[i++] = '-';				// insert '-' into s if n was negative

	// reverses the digits
	while(index > 0)
		s[i++] = temp[--index];			// copy digits from temp to s backwards

	s[i] = '\0';					// null-terminate s, making it a C-string

	return s;					// return s as a convenience
}

Processing the number from the left to the right allows the function to append characters at the end of the string, reducing the temporary storage and eliminating the need to reverse the processed string. However, two aspects of this approach complicate the function. First, the function uses the C-string concat function to append the converted characters. The function's prototype, char* strcat(char* dest, const char* source );, underscores the problem: source is a C-string, not a single character. Second, the process of isolating each digit assumes an understanding of the positional number system (aka a place-value notation). While the positional system is familiar to most software developers, the isolation process uses some mathematics that are possibly less familiar.

char* itoa(int n, char* s)						// convert n to a string, store it in s
{
	char	temp[2];						// converts a character to a C-string
	s[0] = temp[1] = '\0';						// null-terminates s and temp

	if (n == 0)							// returns '0' if n is 0
	{
		strcat(s, "0");						// appends '0' to s
		return s;
	}

	if (n < 0)							// captures the sign if n is negative
	{
		strcat(s, "-");						// appends '-' to s
		n = -n;							// makes n positive for processing
	}

	// converts the number to characters from left to right - the function's heart
	for (int digit = (int)log10(n); digit >= 0; digit--)		// iterates through the number's digits
	{
		temp[0] = char((n / (int)pow(10, digit)) % 10 + '0');	// isolates and converts the leftmost digit
		strcat(s, temp);					// appends the character digit to s
	}

	return s;							// return s as a convenience
}

Identifying C-String Palindromes With The Reverse Method

A palindrome is a string that reads the same forwards and backward, suggesting the next solution of the palindrome-number puzzle. The solution copies the candidate string, reverses it, and then compares it to the original string. If the two strings are the same (i.e., if they are equal), then the candidate string is a palindrome, but it's not a palindrome if the strings are not the same. The code for the reverse function follows the second palindrome program.

#define _CRT_SECURE_NO_WARNINGS						// Microsoft only
#include <iostream>
#include <cstring>
using namespace std;

void reverse(char* s);

int main()
{
	for (int number = 1; ; number++)				// (I.i and I.ii)
	{
		int	square = number * number;			// (II)

		//----------------------------------------------	   III
		char	s[100];
		_itoa(square, s, 10);
		//_itoa_s(square, s, 100, 10);

		//----------------------------------------------	   IV - begin case analysis
		if (strlen(s) < 6)					// (IV.i)
			continue;

		if (s[0] == '0' || s[strlen(s) - 1] == '0')		// (IV.ii)
			continue;

		//----------------------------------------------	   IV.iii - palindrome detection
		char	r[100];						// (a)

		strcpy(r, s);						// (b)
		reverse(r);						// (c)

		if (strcmp(s, r) == 0)					// (d)
		{
			cout << number << " " << square << endl;
			break;
		}
	}

	return 0;
}

The reverse Function

void reverse(char* s) // (a) { for (size_t i = 0; i < strlen(s) / 2; i++) // (b) { char temp = s[i]; // (c) s[i] = s[strlen(s) - 1 - i]; // (d) s[strlen(s) - 1 - i] = temp; // (e) } }

General Palindromes

The definition of a palindrome allows phrases, which may include spaces, punctuation, and mixed-case letters. Palindromes typically don't consider these elements. However, if the previous palindrome-detection algorithms filter out these characters and convert alphabetic characters to the same case, either algorithm can detect a general palindrome.

bool is_palindrome(const char* s)
{
	// filter
	char	temp[1000];				// store the filtered C-string

	int j = 0;					// filters out spaces, punctuation, and converts case
	for (size_t i = 0; i < strlen(s); i++)
		if (isalnum(s[i]))
			temp[j++] = tolower(s[i]);
	temp[j] = '\0';					// null terminate temp

	// check for palindrome
	char	r[1000];				// an array to hold the reversed C-string
	strcpy(r, temp);				// copy the candidate temp to r

	reverse(r);					// reverse C-string r

	return strcmp(r, temp) == 0;			// s is a palindrome if r and temp are equal
}

Downloadable C-string palindrome programs and functions