1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|id = def1
|definition ='''Скобочная последовательность''' (анлгангл. ''Bracket Sequences'') {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}
'''Примеры скобочных последовательностей'''
*<tex>(())))(</tex>
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;
}}
'''Примеры правильных скобочный скобочных последовательностей'''
*<tex>((()()()()))</tex>
*<tex>(())(()())</tex>
== Алгоритм проверки правильности скобочной последовательности ==
Пусть нам дана скобочная последовательность, записанная в строку <tex>s</tex>. Возьмем переменную <tex>\mathtt{counter}</tex>, <tex>\mathtt{counter} = 0</tex>, в которой мы будем поддерживать баланс. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем <tex>\mathtt{counter}</tex> на <tex>1</tex>, закрывающую {{---}} уменьшаем на <tex>1</tex>. Если на протяжении всего перебора <tex>\mathtt{counter}</tex> было неотрицательным (не встречалось закрывающих скобок, для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нету нет лишних закрытых скобок), то скобочная последовательность правильна.
===Псевдокод===
В этом случае для проверки надо будет использовать [[Стек | стек]].
== Лексикографический порядок порядок правильных скобочных последовательностей ==
Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так <tex>(\ <\ )</tex>. Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например <tex>(\ <\ [\ <\ )\ <\ ]</tex>.
'''return''' s
Пусть теперь разрешён не один, а <tex>k</tex> типов скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение <tex>d[2n - i + - 1][\rm ndepth]</tex> на величину <tex>k^{(2n - i - 1 - \rm ndepth) / 2}</tex>, чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только <tex>2n - i - 1 - \rm ndepth</tex>, поскольку <tex>\rm ndepth</tex> скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).
Сложность данного алгоритма <tex>O(n^2 + n \cdot k)</tex>.
