20. Gültige Klammern Gegeben ist eine Zeichenkette s, die nur die Zeichen '(', ')', '{', '}', '[' und ']' enthält. Bestimmen Sie, ob die Eingabekette gültig ist. Eine Eingabekette ist gültig, wenn: 1. Offene Klammern müssen mit derselben Art von Klammern geschlossen werden. 2. Offene Klammern müssen in der richtigen Reihenfolge geschlossen werden. 3. Jede schließende Klammer hat eine entsprechende offene Klammer desselben Typs. Beispiel 1: Eingabe: s = "()" Ausgabe: true Beispiel 2: Eingabe: s = "()[]{}" Ausgabe: true Beispiel 3: Eingabe: s = "(]" Ausgabe: false

Для проверки валидности строки с скобками удобно использовать стек. Идея:

• Проходим по символам строки.
• Если символ — открывающая скобка, кладём её в стек.
• Если закрывающая — проверяем, что верхний элемент стека соответствует ей по типу.
• Если нет соответствия или стек пуст, строка невалидна.
• В конце стек должен быть пустым.

Пример на Python:

def isValid(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack

# Примеры
print(isValid("()"))      # True
print(isValid("()[]{}"))  # True
print(isValid("(]"))      # False