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

<wikitex>

Определения

Определение:

Скобочная последовательность — класс комбинаторных объектов, представляющий собой последовательность скобочных символов.

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

• $(())))($
• $)()()))()(()())$

Определение:

Правильная скобочная последовательность - частный случай скобочной последовательности, определяющийся следующими образами: ""(пустая строка) есть правильная скобочная последовательность; правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*) скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;

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

• $((()()()()))$
• $(())(()())$

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

Пусть нам дана скобочная последовательность записанная в строку $s$. Возьмем переменную $a$, $a = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $a$ на $1$, закрывающую - уменьшаем на $1$. Если на протяжении всего перебора $a$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.

псевдокод:

 function check(s: string): boolean;
   var 
     i, a :integer;
     begin
       a := 0
       for i := 1 to length(s) do  {перебираем последовательно все символы строки (подразумевается, что в ней нет символов отличных от "(" и ")")}
         begin
           if s[i] = '(' then  {проверяем символ и производим соответствующие действия над переменной a}
           inc(a)
           else
           dec(a);
           if a < 0 then
           check := false;  
         end;
       if a = 0 then  {проверяем на равенство нулю}
       check := true
       else
       check := false;
     end;

Надо отметить что, скобочные последовательности могут состоять не только из одного типа скобок, при этом недопустимо такое расположение, когда один тип скобок закрывает другой:

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

• $()[()]\{()()[]\}$ - верно
• $[(]\{\})$ - неверно

В этом случае для проверки надо будет использовать стек.

Лексикографический порядок порядок правильных скобочных последовательностей

Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "0", а закрывающуюся как "1"(**). Тогда первая последовательность с n открывающимися скобками будет иметь вид:

(	(	(	(	...	(	(	(	)	)	)	...	)	)	)	)	(***)
0	0	0	0	...	0	0	0	1	1	1	...	1	1	1	1

что соответствует самому маленькому возможному числу, а последняя:

(	)	(	)	...	(	)	(	)	(	)	...	(	)	(	)
0	1	0	1	...	0	1	0	1	0	1	...	0	1	0	1

что соответствует самому большому возможному числу. Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".

Примеры лексикографического порядка для $n$ и $k$, где $n$ - число открывающихся скобок, а $k$ - число видов скобок

$n = 3$	$k = 1$
$((()))$	$(()())$	$(())()$	$()(())$	$()()()$

$n = 2$	$k = 2$
$()[]$	$([])$	$[()]$	$[]()$

Алгоритм генерации лексикографического порядка будет предложен ниже.

Количество правильных скобочных последовательностей. Числа Каталана

Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.

Определение:

Числа Каталана — последовательность чисел, выражающих: количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями; количество способов соединения 2n точек на окружности n непересекающимися хордами; количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями; количество правильных скобочных последовательностей имеющих n открывающихся скобок.

Числа Каталана удовлетворяют следующему рекурентному соотношению:

$C_0 = 1$; — так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустая

$C_n = \sum_{i = 1}^{n - 1} C_i * C_{n - 1 - i}$.

Это соотношение легко получается из (*). Для этого надо перебрать все возможные последовательности $d_1$ и $d_2$, являющиеся правильными скобочными последовательностями, такие, что $(d_1)d_2$ образуют новые правильные скобочные последовательности необходимой нам длины.

Алгоритмы для генерации следующей правильной скобочной последовательности в лексекографическом порядке и самого лексикографического порядка

Генерация следующей скобочной последовательности:

Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то - "No solution". Воспользуемся интерпретацией (**). Чтобы получить следующий битовый вектор надо найти самый последний нулевой элемент, заменить его на единицу, а элементы следующие за ним сделать минимально возможными (все нули). Тоже самое и со скобочными последовательностями, только после замены нуля на единицу оставшиеся скобки надо расположить в минимальном порядке (в виде (***)):

 function next(var s: string): boolean;
   var 
     i, k, l:integer;    
   begin  
     k := 0;  {счетчик для закрывающихся скобок}
     l := 0;  {счетчик для закрывающихся скобок}
     for i := length(s) downto 1 do  {Начинаем перебирать скобки с конца}
       begin
         if s[i] = '(' then 
           begin
             inc(l);  
             if k > l then  {встретив открывающуюся скобку, которую можно поменять на закрывающуюся, меняяем ее и выходим из цикла}
             break;
           end 
         else 
         inc(k);
       end;
     delete(s, length(s) - l - k + 1, k + l);  {удаляем все скобки включая открывающуюся}
     if s =  then
     next := false
     else
       begin
         s := s +')';  {записываем закрывающуюся скобку}
         for j := 1 to l do  {расставляем скобки в минимально возможном порядке}
         s := s + '(';
         for j := 1 to k - 1 do
         s := s + ')';
         next := true;
       end;
   end;

Если эта функция после выполнения выводит $true$ тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".

Получение лексикографического порядка:

Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:

 procedure (n: integer);
   var
     s: string;
     j: integer;
     t: boolean;
     begin
       s := ;
       if n = 0 then
       writeln()
       else
         begin
           for j := 1 to n do  {создаем начальную строку}
           s := s + '(';
           for j := 1 to n do
           s := s + ')';
           writeln(s);
           t := next(s);
           while t <> false do  {выполняем до тех пор пока не будет получена последняя последовательность}
             begin
               writeln(s);
               t := next(s);
             end;
         end;
     end;

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