1. Welt
  2. Quests
  3. #1441
Alexander Fufaev

Palindrome erkennen - Algorithmus mit Stacks

aus dem Bereich: Quests
Optionen

Deine Aufgabe ist...

Schreibe einen Algorithmus, der als Input einen Array A bekommt und überprüft, ob es sich um ein Palindrom handelt. Jedes Element des Arrays A ist ein einzelnes Zeichen (char), wie z.B. A = ["a", "b", "c"]. Nutze dazu eine beliebige Programmiersprache oder Pseudocode und Stapelspeicher-Datenstruktur bestehend nur aus einem Stack.

Allgemeine Lösungstipps

Ein Palindrom ist ein Wort, welches sowohl vorwärts als auch rückwärts gelesen gleich ist. Beispiele für Palindrome als Arrays: A = ["r", "e", "n", "t", "n", "e", "r"] A = ["o", "t", "t", "o"]

Lösung anzeigen palindromCheck(Array A):
   Stack s = new Stack()
   int n = 0
   n = A.size()

   for i in A do
     s.push(i)

   for i = 0 to n do
     if A[i] == top() then
       s.pop()

   if s.isEmpty() then
     return "Es ist ein Palindrom!"
   else
     return "Es ist kein Palindrom!"

An die Funktion "palindromCheck" wird ein Array A mit einzelnen Zeichen übergeben. In dieser Funktion wird zuerst ein Stack s und ein Integer n initialisiert. Dabei wird n die Länge des Arrays A zugewiesen.

In der ersten for-Schleife werden alle Zeichen des Arrays auf den Stack gelegt. Das nullte Zeichen im Array wird somit zum untersten Objekt auf dem Stack.

In der zweiten for-Schleife, die die Länge des Arrays (n-mal) durchläuft, wird überprüft, ob das oberste Element auf dem Stack dem nullten, ersten, zweiten usw. Zeichen des Arrays entspricht. Wenn das oberste Zeichen auf dem Stack mit dem entsprechenden Zeichen im Array übereinstimmt, wird das oberste Zeichen auf dem Stack entfernt.

Wenn am Ende der Schleife, keine Zeichen auf dem Stack übrig geblieben sind, der Stack also leer ist, muss das Array ein Palindrom sein; ansonsten ist es kein Palindrom.

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 7
Gäste online: 7
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.