Тема: Восстановление правильной скобочной последовательности по шаблону

Где можно прочитать про этот алгоритм? Подскажите, пожалуйста, какие-нибудь книжки или форумы.

2

Re: Восстановление правильной скобочной последовательности по шаблону

А что за задача?

Re: Восстановление правильной скобочной последовательности по шаблону

Денис обнаружил ошибку в своей программе, которая удаляет все символы кроме "(" и ")". Оказывается, некоторые символы заменяются на что-то нечитаемое.
Теперь его заинтересовал вопрос, сколько различных правильных скобочных последовательностей длины 2n могут являться результатом исправленного алгоритма, то есть не будут противоречить данным, которые он потерял.

Формат входного файла
Единственная строка входного файла содержит строку из круглых скобок и знаков вопроса, где вопросами обозначены утраченные символы. Длина строки не превосходит 10000

Формат выходного файла
Выведите одно число - количество различных скобочных последовательностей, удовлетворяющих шаблону Дениса

4

Re: Восстановление правильной скобочной последовательности по шаблону

Подсказка - сначала разберитесь с более простой задачей - как определить, является ли правильной последовательность левых и правых скобок.
После этого можно решать данную задачу -  динамическое программирование, заполнение двумерной таблицы