Верификация правильности размещения скобок в строке

Условие

Необходимо проверить, корректно ли построена строка, содержащая только скобки «()», «[]», «{}». Строка считается корректной, если:

• Каждая открывающая скобка имеет соответствующую закрывающую скобку того же типа.
• Закрывающие скобки появляются в правильном порядке, то есть последняя открытая скобка должна закрываться первой.
• Все открывающие скобки находятся внутри пар скобок того же типа. Примеры: Input: s = "()" Output: true

Example 2: Input: s = "(]" Output: false

Example 3: Input: s = "{[()]}" Output: true

Example 4: Input: s = "[(])" Output: false

Ответ

Используйте стек: открывающие скобки добавляйте в него, а для закрывающей проверяйте последнюю открытую. В конце стек должен быть пустым.

Пример на Python:

def valid_brackets(text):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            return False
    return not stack

Каждая скобка обрабатывается один раз: время O(n), дополнительная память O(n). Пустая строка корректна. Условие о вложенности не означает, что внутри круглых скобок разрешены только круглые: {[()]} тоже корректно.