Задание 24 ЕГЭ: скобочная последовательность

Скобочная последовательность. Тема номера — обработка символьных строк. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Текстовый файл 24.txt содержит строку из 20 000 символов — открывающих и закрывающих круглых и квадратных скобок.

Определите максимальное количество идущих подряд символов, которые образуют правильную скобочную последовательность.

Правильная скобочная последовательность — это последовательность, в которой каждой открывающей скобке соответствует закрывающая того же вида после неё и пары скобок не пересекаются: например, ([]()) — правильная, а ([)] и (] — нет.

Для выполнения этого задания следует написать программу.

Скачать файл к примеру

Решение

Используем стек индексов. На дне стека лежит «барьер» — позиция, перед которой правильный фрагмент начаться не может (сначала −1). Открывающую скобку кладём в стек. Закрывающую, если на вершине парная ей открывающая, снимаем — тогда правильный фрагмент тянется от элемента, оставшегося на вершине, до текущей позиции. Иначе текущая позиция становится новым барьером.

Ответ: 28.

s = open("24.txt").read().strip()
pair = {")": "(", "]": "["}
stack = [-1]
best = 0
for i, c in enumerate(s):
    if c in pair.values():
        stack.append(i)
    elif stack[-1] >= 0 and s[stack[-1]] == pair[c]:
        stack.pop()
        best = max(best, i - stack[-1])
    else:
        stack.append(i)     # непарная закрывающая — барьер
print(best)

Решить такую задачу — новый вариант с проверкой