Правильная скобочная последовательность

Условие

Правильная скобочная последовательность

Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок '(', ')', '{', '}', '[', ']'. Программа должна определить, является ли данная скобочная последовательность правильной.

• Пустая последовательность является правильной.
• Если A — правильная последовательность, то последовательности (A), [A], {A} — правильные.
• Если A и B — правильные последовательности, то последовательность AB — правильная.

Формат ввода: В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок.

Формат вывода: Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.

Ответ

Используйте стек открывающих скобок. Каждая закрывающая должна соответствовать верхней; после обработки всех символов стек обязан быть пуст.

import sys

s = sys.stdin.readline().rstrip('\r\n')
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
valid = True
for char in s:
    if char in '([{':
        stack.append(char)
    elif char in pairs:
        if not stack or stack.pop() != pairs[char]:
            valid = False
            break
    else:
        valid = False
        break
print('yes' if valid and not stack else 'no')

Время O(n), память O(n). Проверка только количества скобок недостаточна: последовательность ([)] имеет равные количества, но неправильную вложенность. Пустая строка корректно даёт yes.