Thread: Removing Specific Characters from Strings

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    3

    Removing Specific Characters from Strings

    I have an algorithm which parses a string to test for a palindrome. Essentially what I want to do is see if the first and last characters of the string are equivalent. If this is the case, then I would want to remove the first and last characters of the string and pass that string to the function again in a recursive call.

    Code:
    bool isPalindrome(string inString)
    {
    	// variable declarations
    	char firstChar = inString.at(0); // the first character in the string
    	char lastChar = inString.at((int)inString.length()); // the last character in the string
    	int stringLength = (int)inString.length(); // the length of the string (num of chars)
    	string::iterator firstCharI = inString.begin(); // iterator beginning of the string
    	string::iterator lastCharI = inString.end(); // iterator ending of the string
    	
    	if (inString == "" || stringLength == 1)
    		return (true);
    	else if (firstChar == lastChar)
    	{
    		// hack off the first and last characters of the string
    		inString.erase(firstCharI);
    		inString.erase(lastCharI);
    		
    		// recursive call to isPalindrome
    		return (isPalindrome(inString));	
    	}
    	else
    		return (false);
    }
    Now I've run into a few issues with this code. First I think I'm preforming a bit of overkill here with all of the information I've prepared about the argument inString. I'm primarily pointing at the iterators. But I found that to use the more suitable overridden version of the erase method uses an iterator for single characters. But that really isn't the primary issue.

    The program that this method is coded into compiles fine however when I run the program, with the method above, I get an exception thrown std:ut_of_range which I'm guessing has to do with requested access to an element outside of array bounds, similar to a segmentation fault. Once I got that error, I modified this line in the isPalindrome method:

    Code:
    char lastChar = inString.at((int)inString.length());
    to this:

    Code:
    char lastChar = inString.at((int)inString.length() - 1);
    The program compiled fine however execution terminated with a segmentation fault. I'm not exactly sure why I'm getting this error and I'm not exactly sure how to go about fixing it. If I could have some advice on clearing up this issue I'd appreciate it. Thanks in advance.

  2. #2
    Registered User
    Join Date
    Feb 2009
    Posts
    138
    inString.end() points to one spot past the last character. erasing it doesn't do anything. change that to inString.end()-1 so that it matches inString.length()-1. there's another problem where you try to index the string out of bounds if it's a palindrome. at the end it becomes an empty string but you still try to index at 0 and length()-1. you can fix that by doing the length test first then getting your indexes and iterators.
    Code:
    bool isPalindrome(string inString)
    {
        int stringLength = (int)inString.length();
        if (inString == "" || stringLength == 1) return (true);
        char firstChar = inString.at(0);
        char lastChar = inString.at(stringLength-1);
        string::iterator firstCharI = inString.begin();
        string::iterator lastCharI = inString.end()-1;
        if (firstChar == lastChar)
        {
            inString.erase(lastCharI);
            inString.erase(firstCharI);
            return (isPalindrome(inString));	
        }
        else return (false);
    }

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Of course, you could avoid erasing the string, and just call the next level of isPalindrome() with instring.substr(2, length-2)

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Code:
    bool isPalindrome(string inString)
    Code:
    inString.erase(firstCharI);
    inString.erase(lastCharI);
    Code:
    return (isPalindrome(inString));
    Yog Sothoth!

    This has got to be the worst implementation of this algorithm ever.

    For a nice big string like this you will allocate a total of 24613 bytes over 151 allocations copying 22650 characters from 151 'std::string' objects..stcejbo 'gnirts::dts' 151 morf sretcarahc 05622 gniypoc snoitacolla 151 revo setyb 31642 fo latot a etacolla lliw uoy siht ekil gnirts gib ecin a roF

    Anyway, you have a few problems:

    1) In C++ arrays and most types implementing '$ operator [] (?)', including 'std::string', are zero based.

    2) The 'erase' method of 'std::string' may invalidate iterators other than the one targeting the element erased.

    3) (I'm not sure about this one. It works this way in my library.) The iterator returned by 'container.end()' is not a valid iterator. Using an invalid iterator, including incrementing or decrementing it through addition and subtraction, may yield an invalid iterator.

    Soma

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If it has to be recursive in the first place. And if it has to be, you don't even need a substring: you could just pass a pair of iterators or the string by reference together with a pair of indices showing where you have reached thus far.

    The iterator returned by 'container.end()' is not a valid iterator. Using an invalid iterator, including incrementing or decrementing it through addition and subtraction, may yield an invalid iterator.
    I was under the impression that it would be invalid to dereference the end() iterator, but you can decrement it safely to get to the last but one (provided the container is not empty). In any case there are also reverse iterators, but again I was under the impression that the iterator returned by rbegin under the hood points to end(), except that when dereferenced it accesses the previous item (otherwise iterator returned by rend() would have nowhere to point). But I may be mistaken.
    Last edited by anon; 02-09-2009 at 09:58 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A development process
    By Noir in forum C Programming
    Replies: 37
    Last Post: 07-10-2011, 10:39 PM
  2. Problem with Strings, Please help!
    By varus in forum C++ Programming
    Replies: 8
    Last Post: 11-27-2006, 11:47 PM
  3. Programming using strings
    By jlu0418 in forum C++ Programming
    Replies: 5
    Last Post: 11-26-2006, 08:07 PM
  4. trouble with strings and characters
    By mhenderson in forum C Programming
    Replies: 7
    Last Post: 08-02-2006, 01:29 PM
  5. Strings and Characters in arrays.
    By akidamo in forum C Programming
    Replies: 24
    Last Post: 04-06-2006, 10:11 PM