C++

Forum

 
PPP2 Chapter 18 Exercise 8 (is_palindrome() function number 3)

DragonOsman (715)
This is for the exercise in Chapter 18 where he asks us to modify the is_palindrome() functions from Section 18.7 to take the approach of generating a reverse copy of the string and then comparing the two strings to see if original string is a palindrome. I have an invalid write exception being thrown in that third is_palindrome() function, at the point where I'm trying to use the passed in first and last elements of the string to create an actual string object to generate a reverse copy of.

Here's the function code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = *first + *last;
	char str[str_length];
	int i = 0;
	while (*first != *last)
	{
		str[i] = first[i];
		++i;
		++first;
	}
	str[int(*last)] = '\0';
	std::cout << "\ndebug (is_palindrome() number 3: " << str << '\n';
	char *str_copy = new char[strlen(str) + 1];
	for (std::size_t i = strlen(str) - 1, j = 0; i >= 0; ++j, --i)
	{
		str_copy[j] = str[i];
	}
	std::cout << "\ndebug: (is_palindrome() number 3: " << str_copy << '\n';
	if (strncmp(str, str_copy, strlen(str)) != 0)
	{
		delete[] str_copy;
		str_copy = nullptr;
		return false;
	}
	delete[] str_copy;
	str_copy = nullptr;
	return true;
}


The exception is being triggered at line 18 in the above code. And the string printed at line 14 appears to have some garbage characters that I wasn't expecting.

So what have I done wrong? Could someone please help me out? Thanks in advance.
Last edited on
coder777 (8439)
The problem is line 13: You insert 0 while you use the character as an index, not the index of the last character.

variable length arrays (line 5) are not good either.

EDIT:
I see that you use the character value all the time. The while loop on line 7 has no defined end and may run infinitely.
Last edited on
Thomas1965 (4571)
1
2
 
  const std::size_t str_length = *first + *last;
  char str[str_length];

This is illegal. str_length must be a constant.

const std::size_t str_length = *first + *last;
How is this supposed to work? Imagine you called this function with "tree" so *first = 't' and *last = 'e', 't' + 'e' is 217 which is obviously wrong.
DragonOsman (715)
Thanks for the replies.

So how do I make str_length a constant? And also, what should I do to fix the other problems?

For str_length, is it possible to do a cast to make first and last constexpr and assign them to a constexpr str_length? If not, how should I figure out the length of the string and assign it to a constexpr object?
Last edited on
coder777 (8439)
how should I figure out the length of the string
Well:
1
2
 
	const int str_length = last - first;
	char *str = new char[str_length + 1]; // Note: +1 for the terminating 0


The loop:
1
2
3
4
5
 
	for(int i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length] = '\0';
Last edited on
DragonOsman (715)
Now all but the problem of the length is fixed. It's not taking the last character of the string into the string I'm trying to build for some reason. Like, for example, if I use "draco", it only stores "drac".

Here's the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = last - first;
	char *str = new char[str_length + 1];
	for (std::size_t i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length] = '\0';
	std::cout << "\ndebug (is_palindrome() number 3: " << str << '\n';
	char *str_copy = new char[strlen(str) + 1];
	for (std::size_t i = strlen(str) - 1, j = 0; i >= 0; ++j, --i)
	{
		if (j >= strlen(str))
		{
			break;
		}
		str_copy[j] = str[i];
	}
	str_copy[strlen(str)] = '\0';
	std::cout << "\ndebug: (is_palindrome() number 3: " << str_copy << '\n';
	if (strncmp(str, str_copy, strlen(str)) != 0)
	{
		delete[] str_copy;
		str_copy = nullptr;
		delete[] str;
		str = nullptr;
		return false;
	}
	delete[] str_copy;
	str_copy = nullptr;
	delete[] str;
	str = nullptr;
	return true;
}


Edit: Also, please be sure to help me in a way that I can also learn (and understand) how to do it on my own as well.
Last edited on
coder777 (8439)
It's not taking the last character of the string into the string I'm trying to build for some reason.
The reason is on line 13: the - 1.

You can dramatically reduce the code. For instance, you do not need strlen(str) because you have this information already: str_length

See this:
1
2
3
4
5
6
7
8
9
10
 
bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	while(first < last)
	{
		if(*(first++) != *(--last))
		  return false;
	}
	return true;
}
JLBorges (13770)
> how should I figure out the length of the string

const auto length = last - first + 1 ;


> and assign it to a constexpr object?

Since first and last are not constexpr, the length too would not be constexpr.

Since the length of the string is not constexpr, we can't use a c-style array.
To store a sequence of characters for which the size is known only at run-time,
reasonably people would use either std::string or std::vector<char>

Something along these lines:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
#include <string>
#include <iomanip>

bool is_palindrome( const char *first, const char *last )
	// first points to the first letter, last to the last letter
{
     // take the approach of generating a reverse copy of the string
     std::string rev_str ;
     for( const char* p = last ; p > first ; --p ) rev_str += *p ;
     rev_str += *first ;

     // then comparing the two strings to see if original string is a palindrome.
     return std::string( first, last+1 ) == rev_str ;
}

int main()
{
    // "For example, anna , petep , and malayalam are palindromes,
    // whereas ida and homesick are not."
    for( std::string str : { "anna", "petep", "malayalam", "ida", "homesick" } )
    {
        const char* const first = std::addressof( str.front() ) ; // pointer to first char
        const char* const last = std::addressof( str.back() ) ; // pointer to lasst char
        std::cout << std::quoted(str) << ' ' << std::boolalpha << is_palindrome( first, last ) << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/81c89d23ec71e4b6
DragonOsman (715)
I can't do that in this function. It's taking the first and last characters of a C-style string, specifically, as input. There are two other overloads that I had to change to take the same approach, where one takes a std::string and the other takes a whole C-style string and its length. You should've done this exercise as well, no (@JLBorges)? Did you forget?


// Chapter 18 Exercise 8
// Exercise Specifications
/**
* Rewrite all the functions in §18.7 to use the approach of making a back-
* ward copy of the string and then comparing; for example, take "home" ,
* generate "emoh" , and compare those two strings to see that they are
* different, so home isn’t a palindrome.
*/


The original version of each function was taking the string and iterating until the middle to see if the string is a palindrome.

That's why, as per the specs, I have to change all three functions so that they take the approach of creating a reverse copy of the string and comparing against the original to check if the string is a palindrome. So really, what you two are doing is suggesting that I do something that goes against the exercise specs. Why?

Anyway, there's still a problem that's causing it to freeze after taking input. The debugger isn't telling me what it is for some reason. Here's the code now:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
 
// Osman Zakir
// 10 / 8 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 18 Sections 18.7.1, 18.7.2 and 18.7.3 Palindromes using std::string, Palindromes using arrays and Palindromes using pointers
// Writing and using function to check if given std::string or C-style is a palindrome
// 10 / 15 / 2017
// Chapter 18 Exercise 8
// Exercise Specifications
/**
 * Rewrite all the functions in §18.7 to use the approach of making a back-
 * ward copy of the string and then comparing; for example, take "home" ,
 * generate "emoh" , and compare those two strings to see that they are
 * different, so home isn’t a palindrome.
 */

#ifdef _WIN32

#define _CRT_SECURE_NO_WARNINGS

#endif

#include "../../cust_std_lib_facilities.h"
#include <iostream>
#include <algorithm>
#include <vld.h>
#include <cstring>
#include <string>

bool is_palindrome(const std::string &s);
bool is_palindrome(const char s[], int n);
bool is_palindrome(const char *first, const char *last);
std::istream &read_word(std::istream &is, char *buffer, int max);

int main()
{
	std::string str;
	char c_string[5];
	char c_string2[5];

	std::cout << "Give me three strings: ";
	std::cin >> str;
	std::cin >> c_string;
	std::cin >> c_string2;
	for (int i = 0; i < strlen(c_string) && strlen(c_string2); ++i)
	{
		if (c_string[i] >= c_string[strlen(c_string) - 1] || c_string2[i] >= c_string2[strlen(c_string2) - 1])
		{
			char *new_str1 = new char[strlen(c_string) + 1];
			char *new_str2 = new char[strlen(c_string2) + 1];
			memcpy(new_str1, c_string, strlen(c_string) + 1);
			memcpy(new_str2, c_string2, strlen(c_string2) + 1);
			new_str1[strlen(c_string) + 1] = '\0';
			new_str2[strlen(c_string2) + 1] = '\0';
			strcpy(c_string, new_str1);
			strcpy(c_string2, new_str2);
			delete[] new_str1;
			delete[] new_str2;
			new_str1 = nullptr;
			new_str2 = nullptr;
		}
	}

	std::cout << "The string " << str << " is";
	if (is_palindrome(str))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	std::cout << "The string " << c_string << " is";
	if (is_palindrome(c_string, strlen(c_string)))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	std::cout << "The string " << c_string2 << " is";
	if (is_palindrome(&c_string2[0], &c_string2[strlen(c_string2) - 1]))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << "not a";
	}
	std::cout << "palindrome\n";
	keep_window_open();
}

bool is_palindrome(const std::string &s)
{
	std::string copy_s{ s };
	std::reverse(copy_s.begin(), copy_s.end());
	if (copy_s != s)
	{
		return false;
	}
	return true;
}

bool is_palindrome(const char s[], int n)
	// s points to the first character of an array of n characters
{
	char *copy_s = new char[n + 1];
	
	for (int i = n - 1, j = 0; i >= 0; --i, ++j)
	{
		copy_s[j] = s[i];
	}

	if (strncmp(s, copy_s, n) != 0)
	{
		delete[] copy_s;
		copy_s = nullptr;
		return false;
	}
	delete[] copy_s;
	copy_s = nullptr;
	return true;
}

bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = last - first;
	char *str = new char[str_length + 1];
	for (std::size_t i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length + 1] = '\0';
	std::cout << "\ndebug (is_palindrome() number 3: " << str << '\n';
	char *str_copy = new char[str_length + 1];
	for (std::size_t i = strlen(str), j = 0; i > 0; ++j, --i)
	{
		str_copy[j] = str[i];
	}
	str_copy[strlen(str)] = '\0';
	std::cout << "\ndebug: (is_palindrome() number 3: " << str_copy << '\n';
	if (strncmp(str, str_copy, strlen(str)) != 0)
	{
		delete[] str;
		str = nullptr;
		return false;
	}
	delete[] str;
	str = nullptr;
	return true;
}

std::istream &read_word(std::istream &is, char *buffer, int max)
	// read at most max-1 characters from is into buffer
{
	is.width(max);		// read at most max-1 characters in the next >>
	is >> buffer;		// read whitespace-terminated word,
						// add NULL-terminating zero after last character read into buffer
	return is;
}


Edit: In my previous run of the program in the debugger, I saw reason to believe that my dynamic C-style string code is wrong. How do I fix it? What am I doing wrong there?
Last edited on
DragonOsman (715)
Okay, now it freezes after reaching line 143 and printing what I'm trying to print there. And the string is coming out as "drago=" when I type "dragon" as the third string. This is the output:
Give me three strings: lalal
petep
dragon
The string lalal is a palindrome
The string petep is a palindrome
The string dragon is
debug (is_palindrome() number 3: drago═

debug: (is_palindrome() number 3:

With the program freezing after that with there being a blinking prompt on the next line.

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
// Osman Zakir
// 10 / 8 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 18 Sections 18.7.1, 18.7.2 and 18.7.3 Palindromes using std::string, Palindromes using arrays and Palindromes using pointers
// Writing and using function to check if given std::string or C-style is a palindrome
// 10 / 15 / 2017
// Chapter 18 Exercise 8
// Exercise Specifications
/**
 * Rewrite all the functions in §18.7 to use the approach of making a back-
 * ward copy of the string and then comparing; for example, take "home" ,
 * generate "emoh" , and compare those two strings to see that they are
 * different, so home isn’t a palindrome.
 */

#ifdef _WIN32

#define _CRT_SECURE_NO_WARNINGS

#endif

#include "../../cust_std_lib_facilities.h"
#include <iostream>
#include <algorithm>
#include <vld.h>
#include <cstring>
#include <string>

bool is_palindrome(const std::string &s);
bool is_palindrome(const char s[], int n);
bool is_palindrome(const char *first, const char *last);
std::istream &read_word(std::istream &is, char *buffer, int max);

int main()
{
	std::string str;
	char c_string[50];
	char c_string2[50];

	std::cout << "Give me three strings: ";
	std::cin >> str;
	std::cin >> c_string;
	std::cin >> c_string2;
	for (int i = 0; i < strlen(c_string) && strlen(c_string2); ++i)
	{
		if (c_string[i] >= c_string[strlen(c_string) - 1] || c_string2[i] >= c_string2[strlen(c_string2) - 1])
		{
			char *new_str1 = new char[strlen(c_string) + 1];
			char *new_str2 = new char[strlen(c_string2) + 1];
			memcpy(new_str1, c_string, strlen(c_string) + 1);
			memcpy(new_str2, c_string2, strlen(c_string2) + 1);
			new_str1[strlen(c_string) + 1] = '\0';
			new_str2[strlen(c_string2) + 1] = '\0';
			strcpy(c_string, new_str1);
			strcpy(c_string2, new_str2);
		}
	}

	std::cout << "The string " << str << " is";
	if (is_palindrome(str))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	std::cout << "The string " << c_string << " is";
	if (is_palindrome(c_string, strlen(c_string)))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	std::cout << "The string " << c_string2 << " is";
	if (is_palindrome(&c_string2[0], &c_string2[strlen(c_string2) - 1]))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << "not a";
	}
	std::cout << "palindrome\n";
	keep_window_open();
}

bool is_palindrome(const std::string &s)
{
	std::string copy_s{ s };
	std::reverse(copy_s.begin(), copy_s.end());
	if (copy_s != s)
	{
		return false;
	}
	return true;
}

bool is_palindrome(const char s[], int n)
	// s points to the first character of an array of n characters
{
	char *copy_s = new char[n + 1];
	
	for (int i = n - 1, j = 0; i >= 0; --i, ++j)
	{
		copy_s[j] = s[i];
	}

	if (strncmp(s, copy_s, n) != 0)
	{
		delete[] copy_s;
		copy_s = nullptr;
		return false;
	}
	delete[] copy_s;
	copy_s = nullptr;
	return true;
}

bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = last - first;
	char *str = new char[str_length + 1];
	for (std::size_t i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length + 1] = '\0';
	std::cout << "\ndebug (is_palindrome() number 3: " << str << '\n';
	char *str_copy = new char[str_length + 1];
	for (std::size_t i = strlen(str), j = 0; i > 0; ++j, --i)
	{
		str_copy[j] = str[i];
	}
	str_copy[strlen(str)] = '\0';
	std::cout << "\ndebug: (is_palindrome() number 3: " << str_copy << '\n';
	if (strncmp(str, str_copy, strlen(str)) != 0)
	{
		delete[] str;
		str = nullptr;
		return false;
	}
	delete[] str;
	str = nullptr;
	return true;
}

std::istream &read_word(std::istream &is, char *buffer, int max)
	// read at most max-1 characters from is into buffer
{
	is.width(max);		// read at most max-1 characters in the next >>
	is >> buffer;		// read whitespace-terminated word,
						// add NULL-terminating zero after last character read into buffer
	return is;
}

Last edited on
JLBorges (13770)
> I can't do that in this function. It's taking the first and last characters of a C-style string, specifically, as input.

What difference does that make? The function does not know anything about where these pointers are coming from; what kind of sequence holds this sequence of characters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
#include <string>
#include <iomanip>
#include <cstring>

bool is_palindrome( const char *first, const char *last )
	// first points to the first letter, last to the last letter
{
     // take the approach of generating a reverse copy of the string
     std::string rev_str ;
     for( const char* p = last ; p > first ; --p ) rev_str += *p ;
     rev_str += *first ;

     // then comparing the two strings to see if original string is a palindrome.
     return std::string( first, last+1 ) == rev_str ;
}

int main()
{
    // "For example, anna , petep , and malayalam are palindromes,
    // whereas ida and homesick are not."
    for( const char* const first : { "anna", "petep", "malayalam", "ida", "homesick" } )
    {
        const char* const last = first + std::strlen(first) - 1 ; // pointer to lasst char
        std::cout << std::quoted(first) << ' ' << std::boolalpha << is_palindrome( first, last ) << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/0442bb999df44b52
DragonOsman (715)
But isn't that cheating? Although I'm not sure if I'm actually allowed to do it like that or not.

And note that when I said that, I was talking to both you and Coder, not just you or him.

And please read my other post from just now as well.

Edit: Also, how does the part on lines 22 and 24 work? Could you please explain? Does it take one string from "first" at a time?
Last edited on
coder777 (8439)
So really, what you two are doing is suggesting that I do something that goes against the exercise specs. Why?
I've never read that book.

Notice line 86: Why the - 1?

Actually, you do not fullfill the exercise specifications because you make two copies. See the function

bool is_palindrome(const char s[], int n)

The difference to your actual function is that you need to calculate the length of the string otherwise it is basically the same.

Consider this:
1
2
3
4
5
6
 
	const bool is_ok = (0 == strncmp(s, copy_s, n));

	delete[] copy_s;
	copy_s = nullptr;

	return is_ok;
DragonOsman (715)
JLBorges has read it. And I did show the exercise specs, so "haven't read it" is not a good excuse. Sorry.

Notice line 86: Why the - 1?

It's because it's the last character and the last character is always at index n-1 (right?).

And how is is_palindrome(const char s[], int n) making two copies? Isn't the loop in that function just reversing the one copy? How would there be two copies?

Edit: Update:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
// Osman Zakir
// 10 / 8 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 18 Sections 18.7.1, 18.7.2 and 18.7.3 Palindromes using std::string, Palindromes using arrays and Palindromes using pointers
// Writing and using function to check if given std::string or C-style is a palindrome
// 10 / 15 / 2017
// Chapter 18 Exercise 8
// Exercise Specifications
/**
 * Rewrite all the functions in §18.7 to use the approach of making a back-
 * ward copy of the string and then comparing; for example, take "home" ,
 * generate "emoh" , and compare those two strings to see that they are
 * different, so home isn’t a palindrome.
 */

#ifdef _WIN32

#define _CRT_SECURE_NO_WARNINGS

#endif

#include "../../cust_std_lib_facilities.h"
#include <iostream>
#include <algorithm>
#include <vld.h>
#include <cstring>
#include <string>

bool is_palindrome(const std::string &s);
bool is_palindrome(const char s[], int n);
bool is_palindrome(const char *first, const char *last);

int main()
{
	std::string str;
	char c_string[50];
	char c_string2[50];

	std::cout << "Give me three strings: ";
	std::cin >> str;
	std::cin >> c_string;
	std::cin >> c_string2;
	std::cout << "The string " << str << " is";
	if (is_palindrome(str))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	std::cout << "The string " << c_string << " is";
	if (is_palindrome(c_string, strlen(c_string)))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	std::cout << "The string " << c_string2 << " is";
	if (is_palindrome(&c_string2[0], &c_string2[strlen(c_string2)]))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << "not a";
	}
	std::cout << "palindrome\n";
	keep_window_open();
}

bool is_palindrome(const std::string &s)
{
	std::string copy_s{ s };
	std::reverse(copy_s.begin(), copy_s.end());
	if (copy_s != s)
	{
		return false;
	}
	return true;
}

bool is_palindrome(const char s[], int n)
	// s points to the first character of an array of n characters
{
	char *copy_s = new char[n + 1];
	
	for (int i = n - 1, j = 0; i >= 0; --i, ++j)
	{
		copy_s[j] = s[i];
	}

	if (strncmp(s, copy_s, n) != 0)
	{
		delete[] copy_s;
		copy_s = nullptr;
		return false;
	}
	delete[] copy_s;
	copy_s = nullptr;
	return true;
}

bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = last - first;
	char *str = new char[str_length + 1];
	for (std::size_t i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length] = '\0';
	std::cout << "\ndebug (is_palindrome() number 3: " << str << '\n';
	char *str_copy = new char[str_length + 1];
	for (std::size_t i = strlen(str), j = 0; i > 0; ++j, --i)
	{
		str_copy[j] = str[i];
	}
	str_copy[strlen(str)] = '\0';
	std::cout << "\ndebug: (is_palindrome() number 3: " << str_copy << '\n';
	if (strncmp(str, str_copy, strlen(str)) != 0)
	{
		delete[] str;
		str = nullptr;
		delete[] str_copy;
		str_copy = nullptr;
		return false;
	}
	delete[] str;
	str = nullptr;
	return true;
}


It seems to work now, but the reversed string isn't printed on the second debug output. Shouldn't it be printed?

And how do grow the my two C-strings if and as needed without leaking memory?
Last edited on
coder777 (8439)
And how is is_palindrome(const char s[], int n) making two copies?
Your current function makes two copies. So look at that function in order to see how to avoid the second copy.

It's because it's the last character and the last character is always at index n-1 (right?).
While that is correct, it is not what you want to achieve. You want to provide the size indirectly with this pointer. That is what the standard container do with the end() function.
DragonOsman (715)
I really don't get it. How is it making two copies? And is my third overload also making two copies, then?

Edit: Also, right now the third function isn't correct, either, since it says that "malayalam" is not a palindrome.
Last edited on
DragonOsman (715)
The third function is saying "The string <string> is not a palindrome" because the reverse copy remains empty the whole way through. Why is this happening and how do I fix it?

And why are there two copies in the second function?

Edit: I changed the array and pointer versions. I called the reverse() function with the string used as an initializer for a std::string in the array version. But the pointer one I'm still having trouble with (I tried to follow the same approach as in the array version):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
bool is_palindrome(const char s[], int n)
	// s points to the first character of an array of n characters
{
	char *copy_s = new char[n - 1];
	memcpy(copy_s, s, n);
	copy_s[n] = '\0';
	std::reverse(std::string{ copy_s }.begin(), std::string{ copy_s }.end());
	if (strncmp(s, copy_s, n) != 0)
	{
		delete[] copy_s;
		copy_s = nullptr;
		return false;
	}
	delete[] copy_s;
	copy_s = nullptr;
	return true;
}

bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = last - first;
	char *str = new char[str_length + 1];
	for (std::size_t i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length] = '\0';
	char *str_copy = new char[str_length + 1];
	memcpy(str_copy, str, str_length);
	std::reverse(std::string{ str_copy }.begin(), std::string{ str_copy }.end());
	if (strncmp(str, str_copy, str_length) != 0)
	{
		delete[] str_copy;
		delete[] str;
		str_copy = nullptr;
		str = nullptr;
		return false;
	}
	delete[] str_copy;
	delete[] str;
	str_copy = nullptr;
	str = nullptr;
	return true;
}
Last edited on
DragonOsman (715)
That didn't work at all. I don't know what to do with the pointer version, but I've got the std::string and array versions working now. I saw a memcpy_reverse in SO and took it.

Here's the code now:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
// Osman Zakir
// 10 / 8 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 18 Sections 18.7.1, 18.7.2 and 18.7.3 Palindromes using std::string, Palindromes using arrays and Palindromes using pointers
// Writing and using function to check if given std::string or C-style is a palindrome
// 10 / 15 / 2017
// Chapter 18 Exercise 8
// Exercise Specifications
/**
 * Rewrite all the functions in §18.7 to use the approach of making a back-
 * ward copy of the string and then comparing; for example, take "home" ,
 * generate "emoh" , and compare those two strings to see that they are
 * different, so home isn’t a palindrome.
 */

#ifdef _WIN32

#define _CRT_SECURE_NO_WARNINGS

#endif

#include "../../cust_std_lib_facilities.h"
#include <iostream>
#include <algorithm>
#include <vld.h>
#include <cstring>
#include <string>

void memcpy_reverse(char *dest, const char *source, const int n);
bool is_palindrome(const std::string &s);
bool is_palindrome(const char s[], const int n);
bool is_palindrome(const char *first, const char *last);

int main()
{
	std::string str;
	std::size_t capacity = 50;
	char *c_string = new char[capacity + 1];
	/*
	char *c_string2 = new char[capacity + 1];*/

	std::cout << "Give me two strings: ";
	std::cin >> str;
	std::cin >> c_string;
	/*
	std::cin >> c_string2;*/

	std::cout << "The string " << str << " is";
	if (is_palindrome(str))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	std::cout << "The string " << c_string << " is";
	if (is_palindrome(c_string, strlen(c_string)))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << " not a";
	}
	std::cout << " palindrome\n";

	/*std::cout << "The string " << c_string2 << " is";
	if (is_palindrome(&c_string2[0], &c_string2[strlen(c_string2)]))
	{
		std::cout << " a";
	}
	else
	{
		std::cout << "not a";
	}
	std::cout << " palindrome\n";*/
	delete[] c_string;
	c_string = nullptr;
	/*
	delete[] c_string2;
	c_string = nullptr;*/
	keep_window_open();
}

void memcpy_reverse(char *dest, const char *source, const int n)
{
	for (std::size_t i = 0; i < n; ++i)
	{
		dest[i] = source[n - i - 1];
	}
}

bool is_palindrome(const std::string &s)
{
	std::string copy_s{ s };
	std::reverse(copy_s.begin(), copy_s.end());
	if (copy_s != s)
	{
		return false;
	}
	return true;
}

bool is_palindrome(const char s[], const int n)
	// s points to the first character of an array of n characters
{
	char *copy_s = new char[n + 1];

	memcpy_reverse(copy_s, s, n);

	if (strncmp(s, copy_s, n) != 0)
	{
		delete[] copy_s;
		copy_s = nullptr;
		return false;
	}
	delete[] copy_s;
	copy_s = nullptr;
	return true;
}

bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = last - first;
	char *str = new char[str_length + 1];
	for (std::size_t i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length] = '\0';
	char *str_copy = new char[str_length + 1];
	memcpy_reverse(str_copy, str, str_length);
	if (strncmp(str, str_copy, str_length) != 0)
	{
		delete[] str_copy;
		delete[] str;
		str_copy = nullptr;
		str = nullptr;
		return false;
	}
	delete[] str_copy;
	delete[] str;
	str_copy = nullptr;
	str = nullptr;
	return true;
}


I need to how to create the string in the pointer version correctly so I can make a reverse copy of it. Right now it's either triggering a breakpoint in some cases or producing an empty string in others.

Edit: Never mind. It's working now. Here are the functions themselves, for reference:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
void memcpy_reverse(char *dest, const char *source, const int n)
{
	for (std::size_t i = 0; i < n; ++i)
	{
		dest[i] = source[n - i - 1];
	}
}

bool is_palindrome(const std::string &s)
{
	std::string copy_s{ s };
	std::reverse(copy_s.begin(), copy_s.end());
	if (copy_s != s)
	{
		return false;
	}
	return true;
}

bool is_palindrome(const char s[], const int n)
	// s points to the first character of an array of n characters
{
	char *copy_s = new char[n + 1];
	memcpy_reverse(copy_s, s, n);
	copy_s[n] = '\0';
	if (strncmp(s, copy_s, n) != 0)
	{
		delete[] copy_s;
		copy_s = nullptr;
		return false;
	}
	delete[] copy_s;
	copy_s = nullptr;
	return true;
}

bool is_palindrome(const char *first, const char *last)
	// first points to the first letter, last to the last letter
{
	const std::size_t str_length = last - first;
	char *str = new char[str_length + 1];
	for (std::size_t i = 0; i < str_length; ++i)
	{
		str[i] = first[i];
	}
	str[str_length] = '\0';
	std::cout << "\ndebug (is_palindrome() number 3: " << str << '\n';
	char *str_copy = new char[str_length + 1];
	memcpy_reverse(str_copy, str, str_length);
	str_copy[strlen(str)] = '\0';
	std::cout << "\ndebug: (is_palindrome() number 3: " << str_copy << '\n';
	if (strncmp(str, str_copy, strlen(str)) != 0)
	{
		delete[] str;
		str = nullptr;
		delete[] str_copy;
		str_copy = nullptr;
		return false;
	}
	delete[] str;
	str = nullptr;
	delete[] str_copy;
	str_copy = nullptr;
	return true;
}
Last edited on
coder777 (8439)
And why are there two copies in the second function?
I never said that. There are two copies in the third function. You should tell when a copy is done. Take a look at the third function. Where are the two copies?

More so: The second and the third function are that similar that the code should look almost the same. Actually the third function can call the second!

1
2
3
4
5
 
bool is_palindrome(const char *first, const char *last) // Third function
	// first points to the first letter, last to the last letter
{
  return is_palindrome(first, last - first); // Calls the second function
}
DragonOsman (715)
Man, that's the simplest possible solution. Thanks for that. I can't believe I didn't notice.

But there shouldn't two copies anywhere now, right? See my most recent solution.

They're so similar that if done correctly, they should be almost the same? So, are they in my solution?

And if that's a yes, I can change the third one to the simpler solution you proposed without worries (because I want to be able to do it correctly the other way as well).
Topic archived. No new replies allowed.