Algorithmen und Datenstrukturen

Stack

Ein Stack ist eine der beliebtesten Datenstrukturen in Algorithmen. Der entscheidende Punkt ist, dass das zuletzt hinzugefügte Element immer als erstes entfernt wird. Man kann sich das wie einen Stapel Teller vorstellen: Nur der oberste Teller kann abgenommen werden, bis alle Teller darüber entfernt sind.
Ein Stack kann in vielen praktischen Situationen zum Einsatz kommen. So kann zum Beispiel die Verlaufsliste in einem Webbrowser als Stack genutzt werden: Wenn du auf den Zurück-Button klickst, führt dich der Browser zur letzten Seite aus dem Stapel. Drückst du erneut auf Zurück, wird die nächste Seite vom Stapel entfernt und du gelangst wieder zur vorherigen Seite.
notion image
Es gibt verschiedene Möglichkeiten, einen Stack in einer Sprache wie Python umzusetzen:
  1. Mit einem list-Objekt – das oberste Element des Stacks ist das letzte Element in der Liste. Wir können mit append hinzufügen, mit pop entfernen und mit [-1] darauf zugreifen.
  1. Mit deque aus collections – hier lassen sich Elemente am Anfang und am Ende hinzufügen und entfernen.
  1. Mit LifoQueue aus dem Modul queue – „Last-In-First-Out“-Warteschlange, was dem Grundprinzip eines Stacks entspricht.
from queue import LifoQueue
stack = LifoQueue()

# push
stack.put(1)
stack.put(2)
stack.put(3)

# pop
print(stack.get())      # gibt 3 aus
print(stack.get())      # gibt 2 aus

# peek
print(stack.queue[-1])  # gibt 1 aus
print(stack.empty())    # prüft, ob leer -> gibt False aus
# Using a simple list
stack = []

# push
stack.append(1)
stack.append(2)
stack.append(3)

# pop
print(stack.pop())      # gibt 3 aus
print(stack.pop())      # gibt 2 aus

# peek
print(stack[-1])        # gibt 1 aus
print(len(stack) == 0)  # prüft, ob leer -> gibt False aus

Herausforderung: Überprüfen, ob die Klammersequenz gültig ist

Gegeben ist eine Folge von Klammern eines mathematischen Ausdrucks (z.B. (()())). Es soll überprüft werden, ob diese Klammerfolge gültig ist. Eine Klammersequenz ist gültig, wenn jede öffnende Klammer eine zugehörige schließende Klammer hat und keine zusätzlichen öffnenden oder schließenden Klammern vorhanden sind.

Eingabe

Die einzige Zeile der Eingabe enthält die Zeichenkette b (1 ≤ |b| ≤ ) mit der Klammersequenz.

Ausgabe

Das Programm soll Yes ausgeben, wenn die Klammersequenz gültig ist, oder No, falls sie ungültig ist.

Beispiele

Eingabe
Ausgabe
()()
Yes
())()(
No
((()())())
Yes
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue