Stos: sprawdzanie nawiasów

Stos, kolejka i odwrotna notacja polska - Algorytmy: zakres rozszerzony (Python)

**Stos** to struktura, w której ostatni odłożony element zdejmujemy jako pierwszy (jak talerze). W Pythonie stosem jest lista: `append` odkłada, `pop` zdejmuje. Nawiasy są poprawne, gdy każdy zamykający pasuje do ostatnio otwartego, który jeszcze nie został zamknięty. Otwierające odkładamy na stos, przy zamykającym zdejmujemy wierzch i sprawdzamy, czy pasuje.

PAIRS = {")": "(", "]": "[", "}": "{"}


def balanced(text):
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        elif char in PAIRS:
            if not stack or stack.pop() != PAIRS[char]:
                return False
    return not stack


for text in ["(a[b]c)", "([)]", "((x)", "{[()()]}"]:
    print(text, balanced(text))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.