Palindrome erkennen

tobmes

Hi,

ich versuche gereade ein kleines Programm zu verfassen, welches vom Benutzer eine Stringeingabe verlangt und dann Prüft, ob die Eingabe ein Palindrom ist.

Bis jetzt habe ich das hier geschriben:

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {

    string eingabe;
    string reverse;
    int j;
    cout << "Bitte geben Sie einen Satz oder ein Wort ein: ";
    cin >> eingabe;

    cout << eingabe.at(2);

    for (int i = eingabe.length(); i>=0, j <= eingabe.length(); i--, j++) {
        eingabe[i -1 ] = reverse[j];
    }

    if (eingabe.compare(reverse) == 0)
        cout "Eingabe ist ein Palindrom!" << endl;
    return 0;
}

Doch leider wird nichts in reverse geschrieben. Kann mir da evtl. jemand helfen?

Danke schon mal.

Du schreibst in Speicher der dir nicht gehört. string reverse hat die Länge 0, damit ist der Zugriff reverse[j] ungültig. Du kannst mit reverse.resize(eingabe.size()); oder so Speicher in reverse reservieren. Das würde man auch alles anders leichter hinkriegen, aber probier erstmal selbst.

if (std::equal(eingabe.begin(), eingabe.begin()+eingabe.size()/2, eingabe.rbegin())
        cout << "Eingabe ist ein Palindrom!" << endl;

tobmes

Hi nwp3,

danke für deine schnelle Antwort. So hat es geklappt. Ich denke, dass wir keine fertigen Funktionen aus c++ verwenden sollen. Aber mich würde dennoch mal der einfache Weg interessieren.

THX

Ich hätte spontan sowas geschrieben:

if (eingabe == string(crbegin(eingabe), crend(eingabe))
    //ist palindrom

oder alternativ damit es nicht nach fertiger Funktion aussieht:

if (eingabe == string(eingabe.crbegin(), eingabe.crend())
    //ist palindrom

Aber das von ungetestet ist eigentlich besser, wenn auch schwerer zu verstehen.

Columbo

Wie wäre es mit einer allgemeinen Lösung:

#include <iostream>
#include <iterator>

template <typename BidirectionalIterator,
          typename Compare>
bool palindrome_impl( BidirectionalIterator first,
                      BidirectionalIterator last,
                      Compare comp,
                      std::bidirectional_iterator_tag )
{
	while( first !=   last
	    && first != --last )
	{
		if( !comp(*first, *last) )
			return false;

		++first;
	}

	return true;
}

template <typename RandomAccessIterator,
          typename Compare>
bool palindrome_impl( RandomAccessIterator first,
                      RandomAccessIterator last,
                      Compare comp,
                      std::random_access_iterator_tag )
{
	while( first < last )
		if( !comp(*first++, *--last) )
			return false;

	return true;
}

template <typename BidirectionalIterator,
          typename Compare>
bool palindrome( BidirectionalIterator first,
                 BidirectionalIterator last,
                 Compare comp )
{
	return palindrome_impl( first, last, comp, typename std::iterator_traits<BidirectionalIterator>::iterator_category{} );
}

template <typename BidirectionalIterator>
bool palindrome( BidirectionalIterator first,
                 BidirectionalIterator last )
{
	using val_type = typename std::iterator_traits<BidirectionalIterator>::value_type;
	return palindrome( first, last, std::equal_to<val_type>{} );
}

#include <string>

int main()
{
	for( std::string t; std::cin >> t; )
		std::cout << /*std::boolalpha <<*/ palindrome(std::begin(t), std::end(t) ) << '\n';
}

Keine Sorge, Volkard - Ich tue jeden Morgen bereits Buße und peitsche mich für mögliche künftigen Untaten aus.

Ethon

Arcoth schrieb:

Wie wäre es mit einer allgemeinen Lösung:

Wow Arcoth, ich als Anfänger habe noch nie so eine tolle Lösung gesehen.
Kannst du mir mal das mit diesem Template-Dingens erklären? Noch nie gemacht.

Columbo

Ethon schrieb:

Kannst du mir mal das mit diesem Template-Dingens erklären? Noch nie gemacht.

Sicher, Ethon!

Zuallerersteinmal sollte erklärt werden, was ein Iterator ist:
Ein Iterator ist die Verallgemeinerung eines Zeigers*. Er verweist auf die Elemente eines Containers, genau wie ein Zeiger auf die Elemente eines Arrays verweist.

In C++ ist es üblich, nicht Container an Algorithmen zu übergeben, sondern Iteratoren, die auf die Elemente verweisen. Das macht es schön allgemein. Nun hat man jedoch das Problem, dass Iteratoren nicht alle denselben Typ haben - ein Iterator für ein Array oder einen vector ist bzw. kann einfach ein Zeiger sein, aber ein Iterator der auf die Elemente einer verketteten Liste verweist - zum Beispiel std::list<int>::iterator - kann unmöglich ein Zeiger sein. Daher nutzt man Templates, um verschiedene Iteratortypen zuzulassen - seien es Klassen, die intern Zeiger auf Listenknoten halten, oder einfache Zeiger. Alles ist möglich, weil ein Funktionstemplate schließlich alle solche Iteratoren als Argumente annehmen kann.

Das Funktionstemplate kann nun mit beliebigen Iteratoren aufgerufen werden, es bestimmt deren Typen automatisch und generiert daraus die passenden Funktionsparameter.
(Dieser Prozess wird Instantiierung genannt, und dazu sagt man dementsprechend auch instantiieren)
Soviel dazu.

Nun gibt es verschiedene Kategorien von Iteratoren. Zum einen gibt es Iteratoren, die man von einander abziehen kann, auf die man eine Zahl draufaddieren kann, oder die man per < vergleichen kann. Der bekannteste dieser Iteratoren, der sogenannten Random-Access-Iteratoren, ist natürlich der Zeiger, der im Grunde nichts als eine Zahl ist.
Dann gibt es Iteratoren, die man nur inkrementieren kann - zum Beispiel die von einer forward_list , einer einfach verketteten Liste.
Und dann gibt es welche, die zwar nicht Random-Access sind, die man aber trotzdem sowohl inkrementieren als auch dekrementieren darf - man kann also in beide Richtungen im Container latschen. Diese Iteratoren nennt man bidirektionale Iteratoren (Bi steht hier für die zwei Richtungen).

Für beide dieser Typen kann man eine unterschiedliche Implementierung schreiben, die prüft, ob die Elemente, auf die die Iteratoren verweisen, ein Palindrom darstellen.

Daher unterscheide ich diese Iterator-Kategorien in meinem Code. Die Technik, die zwischen diesen Kategorien unterscheidet, nennt man Tag Dispatching.

Anschließend biete ich noch die Möglichkeit an, einen eigenen Vergleicher für den Algo zu bestimmen, der auf seine Weise prüft, ob zwei Elemente den gleichen Wert haben.
Auch der Typ des Vergleichers kann beliebig sein (es kann eine Funktion sein, die als Funktionszeiger übergeben wird, oder auch ein Funktor).
Das kann man hübsch ausnutzen, um viele Algorithmen sanft zu vergewaltigen:

for( std::string t; std::cin >> t; )
        std::cout << /*std::boolalpha <<*/ palindrome(std::begin(t), std::end(t), std::not_equal_to{} ) << '\n'; // Prüft, ob ein String ein Anti-Palindrom ist

Falls du nun nicht weißt, was ein Template ist, und daher den Abschnitt der diese beinhaltet nicht verstanden hast, schau in dein Buch.

Du hast noch keins? Sag bloß! Besorg dir eins, hier kannst du suchen,.

* Ja, ich kenne day_iterator und Konsorten, darum geht es hier nicht :p.

Werner Salomon

Hallo Ethon, halle Arcoth,

sehr schön erklärt

Bleibt noch hinzuzufügen:

Arcoth schrieb:

Daher unterscheide ich diese Iterator-Kategorien in meinem Code. Die Technik, die zwischen diesen Kategorien unterscheidet, nennt man Tag Dispatching.

Das Tag Dispatching, so wie es hier verwendet wird, hat den kleinen Nachteil, dass im Falle einer Fehlermeldung des Compilers, der Fehler beim Aufruf von palindrom_impl liegt. Im Falle eines unwissenden Anwender kann das in eine womöglich stundenlange Suche nach dem eigentlichen Problem münden.

Eine etwas moderne Lösung ist mit boost::enable_if möglich, welches mit C++11 auch als std::enable_if im Standard angekommen ist.

Damit sähe es dann so aus:

#include <functional>   // std::equal_to
#include <type_traits> // std::is_base_of
#include <iterator> // std::iterator_traits

template< typename I, typename Pred >
typename std::enable_if< std::is_base_of< std::bidirectional_iterator_tag, typename std::iterator_traits< I >::iterator_category >::value, bool >::type
    palindrome( I first, I last, Pred pred )
{
    for( ; first != last && first != --last; ++first )
        if( !pred( *first, *last ) )
            return false;
    return true;
}

template< typename I >
typename std::enable_if< std::is_base_of< std::bidirectional_iterator_tag, typename std::iterator_traits< I >::iterator_category >::value, bool >::type
    palindrome( I first, I last )
{
    return palindrome( first, last, std::equal_to< typename std::iterator_traits< I >::value_type >() );
}

.. auf den Algorithmus für random_access-Iteratoren habe ich hier verzichtet, ginge aber genauso.

Demo:

#include <iostream>
#include <forward_list>
#include <list>

int main()
{
    using namespace std;
    forward_list< int > fl;
    list< int > l;
    const char text[] = "Otto";

    cout << boolalpha;
    cout << palindrome( fl.begin(), fl.end() ) << endl; // <== compiliert nicht, Compiler Meldung zeigt auf dieses Zeile
    cout << palindrome( l.begin(), l.end() ) << endl;
    cout << palindrome( begin(text), end(text) ) << endl;

    return 0;
}

Gruß
Werner

Columbo

Werner Salomon schrieb:

sehr schön erklärt

Vielen Dank.

Denkst du nicht aber, dass deine Loesung etwas overengineered ist? Man koennte auch ein static_assert in die Definition von palindrome einbauen, wenn es nur um die Fehlermeldung geht?

Arcoth schrieb:

Ethon schrieb:

Kannst du mir mal das mit diesem Template-Dingens erklären? Noch nie gemacht.

Sicher, Ethon!

Ist dein Ironiedetektor kaputt?
Deine Lösung ist der gleiche nutzlose, aufgeblasene Müll wie immer. Overengineered und dem OP wird es absolut garnicht helfen.

DocShoe

Arcoth schrieb:

Werner Salomon schrieb:

sehr schön erklärt

Vielen Dank.

Denkst du nicht aber, dass deine Loesung etwas overengineered ist? Man koennte auch ein static_assert in die Definition von palindrome einbauen, wenn es nur um die Fehlermeldung geht?

MMD!