174
правки
Изменения
Нет описания правки
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $pointer$, $pointer = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $pointer$ на $1$, закрывающую {{---}} уменьшаем на $1$. Если на протяжении всего перебора $pointer$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
'''псевдокод''':
check(s):
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
'''Примеры скобочных последовательностей с несколькими типами скобок:'''
*$()[()]\{()()[]\}$ {{---}} верно
Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
'''Примеры лексикографического порядка для $n$ и $k$, где $n$ {{---}} число открывающихся скобок, а $k$ {{---}} число видов скобок'''
{| border="1" cellpadding="3"
== Алгоритмы генерации ==
'''Генерация следующей скобочной последовательности:'''
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".
'''Получение лексикографического порядка:'''
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
