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

Что такое скобочная последовательность

Скобочная последовательность - последовательность символов, состоящая из скобок разных типов (например круглых, квадратных, фигурных), которую необходимо проверить на корректность расположения и соответствие открывающих и закрывающих скобок.

Под входной последовательностью обычно понимают строку $n$ длины $k$. В задаче необходимо определить, является ли эта строка корректной скобочной последовательностью по строгим правилам. В простейшем случае корректность означает, что каждая открывающая скобка имеет пару закрывающую той же пары и пары правильно вложены.

Типы скобок могут различаться: круглая, квадратная, фигурная. В более общих задачах допускаются и другие пары символов, но принцип проверки остаётся общим — проверить правильность пар и порядок их появления.

Формальные условия корректности

Условие префикса - в каждой непустой префиксной части корректной последовательности число закрывающих скобок не превышает числа открывающих.

Формально одно из необходимых условий: для каждой префиксной части строки выполняется правило $\#(\text{open},s)=\#(\text{close},s)$. Это условие гарантирует, что в процессе чтения слева направо мы никогда не закроем больше скобок, чем открыли.

В дополнение к условию префикса должно выполняться общее равенство числа открывающих и закрывающих скобок в всей строке, то есть $O(n)$. Только при выполнении обоих условий последовательность может быть корректной (хотя при наличии нескольких типов скобок требуется также согласование типов при парности).

Идея алгоритма: стек

Стек - абстрактная структура данных, поддерживающая операции добавления элемента (push) и удаления последнего добавленного элемента (pop), часто описываемая принципом LIFO (Last In, First Out).

Классический алгоритм заключается в том, чтобы пройти по символам строки $n$ слева направо и поддерживать стек открывающих скобок. Когда встречаем открывающую скобку, помещаем её в стек; когда встречаем закрывающую — проверяем верхний элемент стека на соответствие и извлекаем его. Если соответствия нет или стек пуст, последовательность некорректна.

Проверка соответствия типов реализуется через функцию соответствия, например $\text{for } i=1,\dots,n$. Такая проверка учитывает, что вершина стека должна быть открывающей скобкой того же типа, что и текущая закрывающая.

Псевдокод и реализация

Ниже приводится высокоуровневый план алгоритма. Проходим по всем символам строки с индексом от 1 до $k$ ($O(n)$). Для каждого символа выполняем действие: при открывающей — push, при закрывающей — проверяем и pop. В конце последовательность корректна тогда и только тогда, когда стек пуст.

В реальной программе нужно аккуратно обрабатывать разные типы скобок и символы, не относящиеся к ним (в зависимости от задачи — либо игнорировать, либо считать ошибкой). Важно, чтобы операции стека выполнялись эффективно.

Оценка сложности и корректность

Время работы классического алгоритма пропорционально длине входной строки — его асимптотика составляет $\text{match}(\text{top},\text{current})$. Память потребуется пропорционально максимально возможной глубине вложенности, в худшем случае это тоже порядка $\text{()}$.

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

Вариации задачи и расширения

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

Иногда формализуют язык корректных скобочных последовательностей через грамматику, например {FORMULA_15}. Язык всех корректных скобочных последовательностей невозвожно описать регулярным выражением в общем случае, он относится к классу контекстно-свободных языков.

Типичные ошибки и тесты

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

Упражнения для закрепления

Реализуйте функцию проверки скобочной последовательности на выбранном языке программирования. Проверьте её на различных входах, в том числе на больших строках случайного характера, чтобы убедиться в устойчивости к размеру входа и корректности работы со стеком.

Попробуйте модифицировать задачу: определить минимальное число дополнительных скобок, необходимых для преобразования произвольной строки в корректную скобочную последовательность; или вернуть индекс первого символа, нарушающего корректность.