Thread: Recursively Checking a Palindrome string

Hi all.

I have a little problem with a code that checks whether an input string is a palindrome or not. But my problem is that it does not check for the spaces, and I want it to do so.

Here's the code:

Code:

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



int isPalindrome (char *str)
{
	static int length = strlen (str);
	if (length<1)
		return 1;
	if (str[0] == str[length-1])
	{
		length -= 2;
		return isPalindrome (str+1);/*Recursive call as the function isPalindrome 
		is called again within itself*/
	}
	else return 0;
}


int main (void)
{
	int result;
	char str[256];
	printf ("\nPlease type a string: \n");
	gets (str);/*Input a string to check whether it is a palindrome or not*/

	result = isPalindrome (str);/*The function isPalindrome is called.It takes a string 
	argument and returns a value 0 or 1 which is stored in 
	the integer variable "result"*/
	if (result==1) 
		printf ("\n******Input string is a palindrome string.************\n");
	else
		printf ("\n******Not a palindrome******\n");
	return 1;
}

For example, if the input string is:

a man a plan a canal panama

It says that this is NOT a palindrome (spaces problem). I'd be really helpful if anyone sorts this out for me.

Thanks.

Remove your spaces in a tmp string in the isPalindrome() call prior to parsing.

You want

Code:

	
if (length<=1)
  return 1;

Don't use gets(). Use fgets() instead.

There are two ways. One is to copy the input string to another string, char by char, without copying the spaces. The second is to just ignore spaces in your isPalidrome function. Like adding

Code:

if (str[0] == ' ') return isPalindrome(str+1);
if (str[length-1] == ' ') {
   length--;
   return isPalindrome(str);
}

or something similar

A simpler way to do this w/o recursion is using (w/o testing it)

Code:

for(i = 0, j = length - 1; i < length; ;) {
   if (j <= i) break;
   if (str[i] == ' ') {++i; continue; }
   if (str[j] == ' ') {--j; continue; }
   if (str[i] != str[j]) return 0;
   ++i; --j;
}
return 1;

well, don't know if it works, but you get my idea

Either squeeze out the whitespace characters or skip 'em.

Originally Posted by MK27

Here's a function that will strip a list of characters from a string and return the new version:

Code:

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

char *stripchars (char *string, char *list) {
	int len = strlen(string), lsz = strlen(list), c = 0, i, j, flag;
	char tmp[len+1], *new;

	for (i=0;i<len;i++) {
		flag = 0;
		for (j=0;j<lsz;j++) {
			if (string[c] == list[j]) {
				flag = 1;
				break;
			}
		}
		if (!flag) tmp[i] = string[c];
		else { --i; --len; }
		c++;
	}
	tmp[i] = '\0';

	new = malloc(strlen(tmp)+1);
	strcpy(new,tmp);

	return new;
}

int main() {
	char s1[] = "a man a plan a canal panama", *s2;

	s2 = stripchars(s1, " ");
	printf("%s\n%s\n",s1, s2);
	free(s2);

	return 0;
}

Here is my take on this( one of my first coding back in the day)

Code:

/* string and strnospaces have had memory allocated for them prior to this call */
char *
stripspaces (char *string, char *strnospaces)
{
  if (strlen (string) < 1)
    return 0;

  while (*string)
    {
      if (*string == ' ')
        {
          *string++;
        }
      *strnospaces++ = *string++;
    }

  *strnospaces = '\0';

  return strnospaces;

}

I am sure there are a few other ways to address this, perhaps combining lines to shorting line length as well.

Originally Posted by itsme86

What if you have adjacent spaces?

Then just replace the "if" with a "while".

Code:

void filter(char *string, char c){
        int i, o;
        for(i = o = 0; i < strlen(string); i++, o++){
                while(string[i] == c)
                        i++;
                if(i > o)
                        string[o] = string[i];
        }
        string[o] = 0;
}

Here's another version :-)

Thanks a lot everyone. It was of great help.

I've encountered another bit of problem, while running the code in VC++ 6.0. It was fine when I was running it in Code Blocks but in VC it gives the following error with this statement:

Code:

static int length = strlen (str);

ERROR: Initializer is not a constant.

But when I remove the 'static', the output is not right. What should I do?

Originally Posted by itsme86

What if you have adjacent spaces?

Not to hijack this thread. Sorry.

But good call. My big mistake, as issues like this I run into quite often, hehe

Code:

/* fixed */
char *
stripspaces (char *string, char *strnospaces)
{
  if (strlen (string) < 1)
    return 0;

  while (*string)
    {
      if (!(*string == ' '))
        {
          *strnospaces++ = *string;
        }
      *string++;
    }

  *strnospaces = '\0';

  return strnospaces;

}

Originally Posted by itsme86

1) It was a question for slingerland3g about their code.

It's an open forum, anyone can post. I was about to post this anyway and I'm sure slingerland3g can post as well, don't worry.

Originally Posted by itsme86

2) Your answer would fail and run off the end of the string if the last character in the string was a space.

No, that is not correct.

Also, before I leave to catch my train. Below is perhaps a more elaborate, maybe a bit more efficient way of handling palendromes. Though I think there is still an issue with odd length strings

Code:

isPalindrome (char *string)
{
  int BEGINING = 0;
  int LENGTH = (strlen (string)) - 1;

  if (LENGTH < 1)
    return 0;

  /* Watch out for odd palindromes */
  int split = LENGTH / 2;

  do
    {
      if (string[BEGINING] == string[LENGTH - BEGINING]);
      printf ("They are equal %c    %c\n", string[BEGINING], string[LENGTH-BEGINING]);
    }
  while (++BEGINING <= split);

  return 1;

}

That's not a recursive code, is it?

No, I am not calling the function inside thus an iterative method. Though, unless you are required to do this recursively, I would advise against that method for exercises such as this, as it does not lend itself to a recursive method by nature. When you are needing to break down large lists and you are dividing up the load in half at layer of the recursive call, then yes, a recursive method would be ideal but consumes much more stack space.