Determine if a character string is palindromic

  • Thread starter lovecreatesbeauty
  • Start date
L

lovecreatesbeauty

Hello experts,

I write a function named palindrome to determine if a character string
is palindromic, and test it with some example strings. Is it suitable
to add it to a company/project library as a small tool function
according to its quality? I will be very happy to get your suggestion
from every aspect on it: interface design, C language knowledge or
algorithm efficient.

Sincerely,

lovecreatesbeauty


/* Filename : palindrome.c
* Function : bool palindrome(char *s);
* Description: to determine if a character string is palindromic
* Date : 8 May 2006
*/

#include <stdbool.h>
#include <stddef.h>
#include <string.h>

bool palindrome(char *s)
{
bool palindromic = true;
size_t len = strlen(s);

if (len > 1)
{
for (unsigned i = 0; i < len / 2; ++i)
{
if (s != s[len - 1 - i])
{
palindromic = false;
break;
}
}
}

return palindromic;
}


/* test */
#include <stdio.h>

int main()
{
printf("%i\n", palindrome("deed"));
printf("%i\n", palindrome("deeds"));
}

/*
$ gcc -W -Wall -std=c99 -pedantic palindrome.c
$ ./a.out
1
0
$
*/
 
R

Richard Heathfield

lovecreatesbeauty said:
Hello experts,

I write a function named palindrome to determine if a character string
is palindromic, and test it with some example strings. Is it suitable
to add it to a company/project library as a small tool function
according to its quality? I will be very happy to get your suggestion
from every aspect on it: interface design, C language knowledge or
algorithm efficient.


You might want to test it with these well-known palindromes:

"Madam, I'm Adam!"
"Able was I, ere I saw Elba."
"A man, a plan, a canal - Panama!"

Does it correctly identify them as palindromes?

(By the way, that question was rhetorical.)
 
V

Vladimir Oka

lovecreatesbeauty opined:
Hello experts,

I write a function named palindrome to determine if a character
string is palindromic, and test it with some example strings. Is it
suitable to add it to a company/project library as a small tool
function according to its quality? I will be very happy to get your
suggestion from every aspect on it: interface design, C language
knowledge or algorithm efficient.

Sincerely,

lovecreatesbeauty


/* Filename : palindrome.c
* Function : bool palindrome(char *s);
* Description: to determine if a character string is palindromic
* Date : 8 May 2006
*/

#include <stdbool.h>
#include <stddef.h>
#include <string.h>

bool palindrome(char *s)
{
bool palindromic = true;
size_t len = strlen(s);

if (len > 1)
{
for (unsigned i = 0; i < len / 2; ++i)
{
if (s != s[len - 1 - i])
{
palindromic = false;
break;
}
}
}

return palindromic;
}


/* test */
#include <stdio.h>

int main()
{
printf("%i\n", palindrome("deed"));
printf("%i\n", palindrome("deeds"));
}

/*
$ gcc -W -Wall -std=c99 -pedantic palindrome.c
$ ./a.out
1
0
$
*/


Apart from the fact that it doesn't work, it looks fairly good.
Did you consider upper/lower case? Try: "Ana voli Milovana".
Or, alternatively, you need to define "palindrome" more precisely.

--
Microsoft is not the answer.
Microsoft is the question.
NO (or Linux) is the answer.
(Taken from a .signature from someone from the UK, source unknown)

<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>
 
C

CBFalconer

lovecreatesbeauty said:
I write a function named palindrome to determine if a character string
is palindromic, and test it with some example strings. Is it suitable
to add it to a company/project library as a small tool function
according to its quality? I will be very happy to get your suggestion
from every aspect on it: interface design, C language knowledge or
algorithm efficient.

Sincerely,

lovecreatesbeauty

/* Filename : palindrome.c
* Function : bool palindrome(char *s);
* Description: to determine if a character string is palindromic
* Date : 8 May 2006
*/
.... snip code ...

I think you will find the following somewhat simpler. It doesn't
need the C99 stdbool.h include, and guarantees not to modify the
input string. It also handles the silly cases.

#include <stdio.h>
#include <string.h>

/* Returns 1 for palindrome, 0 for non-palindrome */
/* ispalindrome is a reserved function name */
int qpalindrome(const char *s)
{
const char *p;

/* null and empty strings are not palindromes */
if (s && *s) {
p = s + strlen(s) - 1;
while (p > s)
if (*p-- != *s++) return 0;
return 1;
}
return 0;
} /* qpalindrome */

/* It is left as an exercise to allow mixed case. */
/* or to elide blanks */

void check(const char *s)
{
if (s) printf("\"%s\" ", s);
if (qpalindrome(s)) puts("is");
else puts("isn't");
} /* check */

int main(void)
{
puts("Checking palindromes");
check("noon");
check("Noon");
check("dad");
check("Dad");
check(NULL);
check("");
return 0;
} /* main */

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
R

Robert Gamble

lovecreatesbeauty said:
Hello experts,

I write a function named palindrome to determine if a character string
is palindromic, and test it with some example strings. Is it suitable
to add it to a company/project library as a small tool function
according to its quality? I will be very happy to get your suggestion
from every aspect on it: interface design, C language knowledge or
algorithm efficient.

Sincerely,

lovecreatesbeauty


/* Filename : palindrome.c
* Function : bool palindrome(char *s);
* Description: to determine if a character string is palindromic
* Date : 8 May 2006
*/

#include <stdbool.h>

I am not a fan of stdbool.h but that's just me.
#include <stddef.h>
#include <string.h>

bool palindrome(char *s)

If the function does not modify the string pointed to by s (and it
doesn't, I looked ahead), it would be better to indicate this:

bool palindrome (const char *s)
{
bool palindromic = true;
size_t len = strlen(s);

if (len > 1)
{
for (unsigned i = 0; i < len / 2; ++i)

What happens if len/2 > UINT_MAX but less than SIZE_MAX?
I would declare i as size_t.
{
if (s != s[len - 1 - i])
{
palindromic = false;


That's quite a narrow definition of palindrome you have there. A
generally well-accepted definition of palindrome from wikipedia states:

"A palindrome is a word, phrase, number or other sequence of units
(such as a strand of DNA) that has the property of reading the same in
either direction (the adjustment of punctuation and spaces between
words is generally permitted)"

Your example does not allow things like:
"Aba"
"A, A"
which most people would consider to be palindromic.
break;
}
}
}

return palindromic;
}

Below is my version of the function, the main difference is the fact
that it is much less strict than yours ignoring all non-alphanumeric
characters:

#include <stddef.h>
#include <string.h>
#include <ctype.h>

int palindrome(const char *s)
{
size_t len = strlen(s);
const char *left, *right;

if (len > 1) {
left = s; right = s+(len-1);
while (left < right) {
if (!isalnum(*left)) {
left++;
continue;
}
if (!isalnum(*right)) {
right--;
continue;
}
if (toupper(*left) == toupper(*right)) {
left++, right--;
continue;
} else {
return 1;
}
}
}
return 0;
}

/* test */
#include <stdio.h>
#define BUF_SIZE 80

int main(void)
{
char buf[BUF_SIZE];
while (fgets(buf, 80, stdin) != NULL)
palindrome(buf) ? puts("Palindrome") : puts("Not a palindrome");
return 0;
}

Robert Gamble
 
R

Robert Gamble

Robert said:
Below is my version of the function, the main difference is the fact
that it is much less strict than yours ignoring all non-alphanumeric
characters:

#include <stddef.h>
#include <string.h>
#include <ctype.h>

int palindrome(const char *s)
{
size_t len = strlen(s);
const char *left, *right;

if (len > 1) {
left = s; right = s+(len-1);
while (left < right) {
if (!isalnum(*left)) {
left++;
continue;
}
if (!isalnum(*right)) {
right--;
continue;
}
if (toupper(*left) == toupper(*right)) {
left++, right--;
continue;
} else {
return 1;

That should be return 0;
}
}
}
return 0;

And that should be return 1;

Robert Gamble
 
J

john

Robert said:
That should be return 0;


And that should be return 1;

Is there any particular reason that functions often behave this way?
If they succeed, they return 0, which in C is false, and vice versa.

Hmm, while I was writing this it occurred to me that it can have
something to do with error reporting. Different return values can
indicate different errors. Is that the reason?
 
V

Vladimir Oka

john opined:
Is there any particular reason that functions often behave this way?
If they succeed, they return 0, which in C is false, and vice versa.

Hmm, while I was writing this it occurred to me that it can have
something to do with error reporting. Different return values can
indicate different errors. Is that the reason?

Probably because returning 0 from `main()` is an indication of
successful program termination.

--
"Besides, I think [Slackware] sounds better than 'Microsoft,' don't
you?"
(By Patrick Volkerding)

<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>
 
K

Keith Thompson

lovecreatesbeauty said:
I write a function named palindrome to determine if a character string
is palindromic, and test it with some example strings. Is it suitable
to add it to a company/project library as a small tool function
according to its quality? I will be very happy to get your suggestion
from every aspect on it: interface design, C language knowledge or
algorithm efficient.

/* Filename : palindrome.c
* Function : bool palindrome(char *s);
* Description: to determine if a character string is palindromic
* Date : 8 May 2006
*/

#include <stdbool.h>
#include <stddef.h>
#include <string.h>

bool palindrome(char *s)
{
bool palindromic = true;
size_t len = strlen(s);

if (len > 1)
{
for (unsigned i = 0; i < len / 2; ++i)
{
if (s != s[len - 1 - i])
{
palindromic = false;
break;
}
}
}

return palindromic;
}


/* test */
#include <stdio.h>

int main()
{
printf("%i\n", palindrome("deed"));
printf("%i\n", palindrome("deeds"));
}


Your use of <stdbool.h> and of a declaration within a for loop mean
your program will work only with a C99 implementation, or with an
implementation that provides these features as an extension. Only you
can decide whether that's a problem. Converting the program to C90,
or rather to the common subset of C90 and C99, is straightforward.

You use an unsigned object to iterate through the string, but the
upper bound of the iteration is of type size_t. It's conceivable that
size_t could be bigger than unsigned, and that your loop could fail
for a very long string. You're unlikely to run into this problem
either in practice or in testing, unless you're specifically looking
for it. On many implementations, you'll never see a problem (i.e.,
testing can never reveal the bug). In other words, this bug is
particularly insidious.

The printf statements invoke undefined behavior. Your palindrome()
function returns a bool; printf's "%i" expects an int.

Note that "%i" is equivalent to "%d" in a printf format string; "%d"
is much more common in my experience. Using "%i" is perfectly correct
(if the corresponding argument is an int), but seeing it forces me to
pause and wonder why the author chose to use "%i" rather than "%d".
Perhaps the author thought there was a difference, and is failing to
express something significant. This is a minor style issue; feel free
to ignore it. (Note that "%d" and "%i" do behave differently in
scanf.)

You haven't defined the term "palindromic". The usual definition
ignores whitespace, punctuation, and the distinction between upper and
lower case; for example, "A man, a plan, a canal, Panama!" is
considered to be a palindrome. If you want to use a simpler
definition, that's fine, but you need to state clearly what definition
you're using.

Finally, the only use I've ever seen for a function to determine
whether a string is a palindrome is as an exercise in a programming
class or other tutorial. I can't imagine including such a function,
however well implemented, in a library, or calling it other than in a
test of the function itself.
 
B

Ben C

Is there any particular reason that functions often behave this way?
If they succeed, they return 0, which in C is false, and vice versa.

Hmm, while I was writing this it occurred to me that it can have
something to do with error reporting. Different return values can
indicate different errors. Is that the reason?

I always assumed that was the basic reason. Occasionally people write
functions that return boolean "true for success", and often functions
that return pointers return NULL for failure, so you always have to be a
bit careful with

if (f())
/* succeeded or failed? */

etc.
 
R

Richard Tobin

/* null and empty strings are not palindromes */

Why on earth would you choose to not call the empty string a
palindrome? That would break such obvious invariants (indeed,
one might say definitions) as

palindrome(s) == (strcmp(s, reverse(s)) == 0)

-- Richard
 
C

Chris F.A. Johnson

Finally, the only use I've ever seen for a function to determine
whether a string is a palindrome is as an exercise in a programming
class or other tutorial. I can't imagine including such a function,
however well implemented, in a library, or calling it other than in a
test of the function itself.

I use one in my work (composing cryptic crosswords).
 
K

Keith Thompson

Chris F.A. Johnson said:
I use one in my work (composing cryptic crosswords).

Ok, sometimes my imagination fails me.

(Chris, just out of curiosity, why do you always indent everything you
write? Indentation like that is sometimes used to denote blocks of
quoted text. IMHO it would be clearer if your text were
left-justified like everyone else's.)
 
C

CBFalconer

Richard said:
Why on earth would you choose to not call the empty string a
palindrome? That would break such obvious invariants (indeed,
one might say definitions) as

palindrome(s) == (strcmp(s, reverse(s)) == 0)

All I can say is I documented it. That has been lying about in my
junk directory for four years. To alter that, simply change 0 to 1
in one location.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
C

Chris F.A. Johnson

Ok, sometimes my imagination fails me.

(Chris, just out of curiosity, why do you always indent everything you
write?

For the same reason that books have margins, and better books wider
margins.

Actaully, I started doing it in order to distinguish between my
text and (shell) code. I like code set flush left so that no
fiddling is necessary when cutting and pasting it.
Indentation like that is sometimes used to denote blocks of
quoted text.

Newsreaders, IME, generally do not recognize indentation as
quoting.
IMHO it would be clearer if your text were left-justified like
everyone else's.)

Left-justified? You mean flush-left and/or ragged right.
 
F

Flash Gordon

Chris said:
For the same reason that books have margins, and better books wider
margins.

My news reader provides such indentation sufficient unto my needs. I
could probably configure it to provide more if I so desired. This does
not require that you indent your text.
Actaully, I started doing it in order to distinguish between my
text and (shell) code. I like code set flush left so that no
fiddling is necessary when cutting and pasting it.

Personally I find shells don't have a problem with white space before
the commands.
Newsreaders, IME, generally do not recognize indentation as
quoting.
Agreed.


Left-justified? You mean flush-left and/or ragged right.

Yes, the normal is flush-left and ragged right. Since it is the norm
news readers can reformat it as well.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
 
C

CBFalconer

Chris F.A. Johnson said:
For the same reason that books have margins, and better books wider
margins.

Actaully, I started doing it in order to distinguish between my
text and (shell) code. I like code set flush left so that no
fiddling is necessary when cutting and pasting it.


Newsreaders, IME, generally do not recognize indentation as
quoting.


Left-justified? You mean flush-left and/or ragged right.

Flush left. Your technique is fine until it gets requoted, when it
tends to spread out to the right, and be resistant to reformatting.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
Q

qed

john said:
Is there any particular reason that functions often behave this way?
If they succeed, they return 0, which in C is false, and vice versa.

Hmm, while I was writing this it occurred to me that it can have
something to do with error reporting. Different return values can
indicate different errors. Is that the reason?

It follows from a tradition in UNIX, however there is also a sound
reason for it. Very often a function returns with the *quantity* of
something it is trying to count from a complex data structure. However,
the data structure may be detectably corrupted or in an ill-defined
state. So using one int return value you can follow the convention that
all negative values indicate errors, and all positive values means
success -- further that all the positive values indicate each possible
count, while different negative values can correspond to different kinds
of errors.

So for example, how many elements are in a vector? Normally, you would
just want to know the quantity of elements that that vector has -- every
possibility from 0 to INT_MAX (say) makes sense, has meaning and easily
corresponds to a successful return. But if the vector is corrupted
because it has been ininitialized, or if an entry has some bad contents
or something like that you probably want some detail to help you track
down what kind of error you have, so that you can debug it, or avoid
that kind of vector contents. If you are just debugging, its usually
convenient to return -__LINE__. You can still reserve the value -1 for
other kinds of deterministic errors (like out of memory), since its
generally not possible to have source code which can expand the macro
__LINE__ on the first line of your source.
 
S

Simon Biber

Richard said:
lovecreatesbeauty said:





You might want to test it with these well-known palindromes:

"Madam, I'm Adam!"
"Able was I, ere I saw Elba."
"A man, a plan, a canal - Panama!"

They are palindromic sentences, not palindromic strings.

void convert_sentence_to_string(char *destination, const char *source)
{
for(; *source; source++)
{
if(isalpha((unsigned char) *source))
*destination++ = toupper((unsigned char) *source);
}
}
 
R

Richard Heathfield

Simon Biber said:
They are palindromic sentences, not palindromic strings.

They are palindromes.
void convert_sentence_to_string(char *destination, const char *source)
{
for(; *source; source++)
{
if(isalpha((unsigned char) *source))
*destination++ = toupper((unsigned char) *source);
}
}

And when were you planning on fixing the bug? :)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top