94
правки
Изменения
Нет описания правки
*"" (пустая строка) есть правильная скобочная последовательность;
*пусть $S$ {{- --}} правильная скобочная последовательность, тогда $(S)$ есть правильная скобочная последовательность;*пусть $SS1$, $S2$ {{--- правильная скобочная последовательность}} правильные скобочные последовательности,тогда $()S$ и $S()S1S2$ есть правильные скобочные последовательностиправильная скобочная последовательность;
}}
''Примеры правильных скобочный последовательностей:''
== Алгоритм проверки правильности скобочной последовательности ==
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $pointer$, $pointer = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $pointer$ на $1$, закрывающую {{- --}} уменьшаем на $1$. Если на протяжении всего перебора $pointer$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
''псевдокод'':
check(s):
pointer = 0
for (i = 1; i < = length(s) + 1; i++):
pointer = (s[i] == '(')? pointer++ : pointer--
if (pointer < 0)
''Примеры скобочных последовательностей с несколькими типами скобок:''
*$()[()]\{()()[]\}$ {{--- }} верно*$[(]\{\})$ {{--- }} неверно
В этом случае для проверки надо будет использовать стек.
Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
''Примеры лексикографического порядка для $n$ и $k$, где $n$ {{- --}} число открывающихся скобок, а $k$ {{--- }} число видов скобок''
{| border="1" cellpadding="3"
*количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями;
*количество способов соединения $2n$ точек на окружности $n$ не пересекающимися хордами;
*количество разбиений выпуклого $(n + 2)$ - угольника на треугольники не пересекающимися диагоналями;
*количество правильных скобочных последовательностей имеющих $n$ открывающихся скобок.}}
Числа Каталана удовлетворяют следующему рекуррентному соотношению:
$C_0 = 1$; {{---}} так как существует только одна скобочная последовательность с $0$ открывающихся скобок {{- --}} пустая
$C_n = \sum_{i = 1}^{n - 1} C_i C_{n - 1 - i}$.
''Генерация следующей скобочной последовательности:''
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{- --}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
next(s):
return false
s = s +')'
for (j = 1; j < = pointer_open + 1; j++):
s = s + '('
for (j = 1; j < pointer_close; j++):
result(s)
else
for (j = 1; j < = n + 1; i++)
s = s + '(';
for (j = 1; j < = n + 1; i++)
s = s + ')';
result(s);
