Recursively Checking a Palindrome string

This is a discussion on Recursively Checking a Palindrome string within the C Programming forums, part of the General Programming Boards category; Hi all. I have a little problem with a code that checks whether an input string is a palindrome or ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    36

    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.

  2. #2
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Remove your spaces in a tmp string in the isPalindrome() call prior to parsing.

  3. #3
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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;
    }
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Either squeeze out the whitespace characters or skip 'em.

  6. #6
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Quote Originally Posted by MK27 View Post
    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.

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    Code:
      while (*string)
        {
          if (*string == ' ')
            {
              *string++;
            }
          *strnospaces++ = *string++;
        }
    What if you have adjacent spaces?
    If you understand what you're doing, you're not learning anything.

  8. #8
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by itsme86 View Post
    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 :-)

  9. #9
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    Quote Originally Posted by Subsonics View Post
    Then just replace the "if" with a "while".
    1) It was a question for slingerland3g about their code.
    2) Your answer would fail and run off the end of the string if the last character in the string was a space.
    If you understand what you're doing, you're not learning anything.

  10. #10
    Registered User
    Join Date
    Aug 2009
    Posts
    36
    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?

  11. #11
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    Quote Originally Posted by itsme86 View Post
    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;
    
    }

  12. #12
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by itsme86 View Post
    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.

    Quote Originally Posted by itsme86 View Post
    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.

  13. #13
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    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;
    
    }

  14. #14
    Registered User
    Join Date
    Aug 2009
    Posts
    36
    That's not a recursive code, is it?

  15. #15
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Error in Recursive String Palindrome Code
    By clegs in forum C Programming
    Replies: 13
    Last Post: 12-21-2008, 11:36 AM
  2. OOP Question DB Access Wrapper Classes
    By digioz in forum C# Programming
    Replies: 2
    Last Post: 09-07-2008, 04:30 PM
  3. Inheritance Hierarchy for a Package class
    By twickre in forum C++ Programming
    Replies: 7
    Last Post: 12-08-2007, 03:13 PM
  4. RicBot
    By John_ in forum C++ Programming
    Replies: 8
    Last Post: 06-13-2006, 06:52 PM
  5. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21