How can I detect a palindrome as complicated as "A man, a plan, a canal, Panama!" without using erase() and just ignore the spaces and punctuations?

The current version is:

#include <stdlib.h>  // system pause
//#inlcude <ctype.h>     // for toupper()
#include <iostream>   // input output
#include <string>

//#include <algorithm>

//#include <iomanip>  // for setw() and right-aligned
//#include <math.h>    // for pow()
using namespace std;


int main()
{
  
  
  /* char alpha [26];
    char ch;
    string txt;
    
    for(int i = 0 ; i <= 25 ; i++)
    {alpha [i] = 'A' + i;
     cout << alpha [i] << " ";}
    
    cout << "\n";
    cout << alpha[4];
    
    
    cout << "Enter a string: ";
    getline(cin, txt);
    
    int max = txt.length();
    for (int j = 0 ; j < max ; j++)
    txt.at(j);
    
    cout << txt;
    
*/
/*

int alpha[26];
string txt;


for(int i = 0 ; i < 26 ; i++)
{
  alpha[i] = 0;
  cout << alpha[i];
}
    
   cout << "\n" ;
    
    
    cout << "Enter your text: ";
    getline(cin,txt);
    int max = txt.length();
    
    for (int j = 0 ; j < max; j++)
    alpha = txt.at(j);
   */ 
    
  
  int alpha[26];
  bool palind = true;
  
  
  for(int i = 0 ; i < 26 ; i++)
  alpha[i] = 0;
  
  
  //string txt = "i love you!";
  string txt;
  string txt1;
  
  cout << "Please enter a text: " << endl;
  getline(cin, txt);
  
 
  // make upper case of txt
  
  
  
  for (int pos = 0 ; pos < txt.length() ; pos++)
  {
      
       txt[pos] = toupper(txt[pos]);
      // cout << txt.at(pos);
  }
  
  cout << "\n";
  // ---------------------------------
  


        for (int pos = 0 ; pos < txt.length() ; pos++)
        {
        
        if (txt[pos] >= 'A' && txt[pos] <= 'Z')
        {
        int x = txt[pos] - 65;
        alpha [x]++;
        }
        else
        {
            //txt[pos] = '\0';
           txt.erase(pos); // get rid of punctuations and spaces
           // txt [txt.length()-1] = '\0';
             
             }
             
        }
       
      
       for (int x = 0,  y = txt.length()-1; x <= (txt.length()/2),y >=0; y--, x++)
       {
           txt1+=txt.at(y);
           
         
}   
    //cout << "txt: " << txt << "txt1:" << txt1;
    
    if (txt1 != txt)
   { palind = false;}
       
       if (palind == true)
       {cout << "Is a palindrome!";}

  cout <<"\n"; 
  int z = 0;
  
  for (z = 0 ; z < 26 ; z++)
  cout << char(z + 65)  << "  " << alpha [z]<< " times in txt " << endl;
  
  
    
    
    
    
    system("pause");
    return 0;
    
    
}



//-------------palindrome

/*
 if (txt.length() == 1)
  {cout << "Is a palindrome";}
  
  
  for (x = 0 , y = (txt.length()) - 1 ; x <= txt.length()/2, y >= txt.length()/2 ; x++, y--)
  {
      
     
     if (txt[x] != txt[y])
     {
              palind = false;
     }
     
  } 
  
  if (palind == true)
  {
             cout << "txt is a palindrom";
             }
             else
             {
                 cout << "it is NOT a palindrome";
                 }


*/

To find out something like your first case you would need to do a couple things. First copy the string backwards into another string. Then start at the beginning of each string and check if the charectures match. I would pass both through either toupper() or tolower() so you can disregard case. If you hit a space or punctuation then skip it and check the next spot in the string.

Start at both ends using 2 index values
If a character is to be ignored, just inc/decrement the index and restart the loop.

You need to apply the following transformation.

1) Remove all nonalpha characters
2) Convert all character to lowercase
3) Compare it to its reverse( or compare begin + i to end - i )

To remove all nonalpha characters to a string you can use the following:

struct IsNotAlpha{
 bool opearator()(const int ch){ return !isalpha(ch); }
};
struct ToLower{
 char operator()(const int ch){ return tolower(ch); }
};
bool isPalin(const std::string& str){
 string res(str);
 //convert all character to lower case
 std::transform( str.begin(), str.end(), res.begin(),ToLower); 
 //erase all character that is not characters
 res.erase(std::remove_if(res.begin(),res.end(),IsNotAlpha), res.end() );
 //compare the string to its transformed reverse
 return str == string(res.rbegin(),res.rend()) ;
}

I'm not sure about it compiling but its just there to give you a general idea.

Edited 5 Years Ago by firstPerson: n/a

Came up with this. Should show you one way of doing it.

template<typename RandomAcessIterator>
bool IsLosePalindrome(RandomAcessIterator start, RandomAcessIterator end)
{
	if (start == end - 1)
		return true;
	end--;
	while (start <= end)
	{
		while (ispunct(*start) || isspace(*start))
			++start;
		while (ispunct(*end) || isspace(*end))
			--end;
		if (tolower(*start) == tolower(*end))
		{
			start++;
			end--;
		}
		else
			return false;
	}
	return true;
}

A more general version of NathanOliver's idea; somewhat academic, and using the boost iterator library.

#include <iterator>
#include <type_traits>
#include <locale>
#include <functional>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <algorithm>
#include <string>
#include <iostream>
#include <list>

namespace
{
  template < typename ITERATOR, typename FILTER, typename TRANSFORM >
  bool _is_palindorome( ITERATOR begin, ITERATOR end, FILTER filter,
                         TRANSFORM transform, std::random_access_iterator_tag )
  {
    const auto N = ( end - begin ) / 2 ;
    std::reverse_iterator<ITERATOR> rbegin(end), rend(begin) ;

    using namespace boost ;
    return std::equal(
      make_transform_iterator( make_filter_iterator(filter,begin,end-N), transform ),
      make_transform_iterator( make_filter_iterator(filter,end-N,end-N), transform ),
      make_transform_iterator( make_filter_iterator(filter,rbegin,rend-N), transform ) ) ;
  }

  template < typename ITERATOR, typename FILTER, typename TRANSFORM >
  bool _is_palindorome( ITERATOR begin, ITERATOR end, FILTER filter,
                         TRANSFORM transform, std::bidirectional_iterator_tag )
  {
    std::reverse_iterator<ITERATOR> rbegin(end), rend(begin) ;

    using namespace boost ;
    return std::equal(
      make_transform_iterator( make_filter_iterator(filter,begin,end), transform ),
      make_transform_iterator( make_filter_iterator(filter,end,end), transform ),
      make_transform_iterator( make_filter_iterator(filter,rbegin,rend), transform ) ) ;
  }
}

template < typename ITERATOR > bool is_palindorome( ITERATOR begin, ITERATOR end,
                                            const std::locale& locale = std::locale() )
{
    typedef typename std::iterator_traits<ITERATOR>::value_type char_type ;

    static const std::function< bool(char_type) > is_alnum =
                        [locale] ( char_type c ) { return std::isalnum(c,locale) ; } ;

    static const std::function< char_type(char_type) > to_lower =
                        [locale] ( char_type c ) { return std::tolower(c,locale) ; } ;

    return _is_palindorome( begin, end, is_alnum, to_lower,
                      typename std::iterator_traits<ITERATOR>::iterator_category() ) ;
}

int main()
{
    const std::string& str = "This is not a palindrome." ;
    std::cout << std::boolalpha << is_palindorome( str.begin(), str.end() ) << '\n' ;
    std::cout << is_palindorome( str.c_str(), str.c_str()+str.size() ) << '\n' ;
    const std::wstring wstr = L"A man, a plan, a canal, Panama!" ;
    std::cout << is_palindorome( wstr.begin(), wstr.end() ) << '\n' ;
    std::list<wchar_t> lst( wstr.rbegin(), wstr.rend() ) ;
    std::cout << is_palindorome( lst.begin(), lst.end() ) << '\n' ;
}
This article has been dead for over six months. Start a new discussion instead.