Palindrome with minimum altering the text!

[henrimontreal]

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";
                 }


*/

[NathanOliver]

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.

[WaltP]

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

[mrnutty]

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.

[NathanOliver]

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;
}

[vijayan121]

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' ;
}