94
правки
Изменения
Нет описания правки
{{Определение
|id = def1
|definition ='''Правильная скобочная последовательность''' {{- --}} частный случай скобочной последовательности, определяющийся следующими образами:
*""(пустая строка) есть правильная скобочная последовательность;
*правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)
*скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;
== Алгоритм проверки правильности скобочной последовательности ==
Пусть нам дана скобочная последовательность , записанная в строку $s$. Возьмем переменную $a$, $a = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $a$ на $1$, закрывающую - уменьшаем на $1$. Если на протяжении всего перебора $a$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
''псевдокод'':
== Лексикографический порядок порядок правильных скобочных последовательностей ==
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "$0$", а закрывающуюся как "$1$" (**). Тогда первая последовательность с $n $ открывающимися скобками будет иметь вид:
{| border="1" cellpadding="3"
