55
правок
Изменения
Нет описания правки
|definition ='''Правильная скобочная последовательность''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:
*<tex>\varepsilon</tex> ("", пустая строка) есть правильная скобочная последовательность;
*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</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>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
Для запуска алгоритма необходимо сделать вызов <tex>\mathrm{gen}(>n</tex>, <tex>0</tex>, <tex>0</tex>, <tex>"")</tex>.
*<tex> \mathtt{ans}</tex> {{---}} строка, в которой мы считаем ответ
*<tex> \mathtt{counter_opencounter\_open}</tex> - количество открывающих скобок в данный момент*<tex> \mathtt{counter_opencounter\_open}</tex> - количество закрывающих скобок в данный момент
'''function''' gen(n: '''int''', counter_open: '''int''', counter_close: '''int''', ans: '''string''')
'''if''' counter_open + counter_close == 2 * n
'''else'''
counter_close++
delete(s, length(s) - counter_open - counter_close, counter_close + counter_open) <span style="color:Green"><br>// начиная с символа с индексом "length(s) - counter_open - counter_close" удаляем все символы (индексация с 0)</span>
'''if''' s == ""
'''return''' "No Solution"
