скобки :)

[Soul]

Есть строка, в которой записаны круглые скобки и знаки вопроса. Нужно вычислить сколькими способами знаки вопроса можно заменить на скобки (открывающую или закрывающую) так, чтобы они составляли правильное выражение.

например:
????(?
ответ
2


Вообще задача по программированию, но у меня сильное ощущение, что перебор в цикле не пройдет по времени (строка до 80 символов, a значит при полном переборе на несколько лет вычислений должно хватить). A потому нужно как-то выразить ответ формулой... есть идеи?

[Draeden]

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

1. Написать нехватающие скобки, останется N свободных мест.
2. Решить задачу: сколько существует правильных последовательностей из N скобок.

[Soul]

Source of the post
Порядок скобок не особо важен, главное, чтоб закрывающие шли за открывающими.
Поэтому предлагаю решать так:

1. Написать нехватающие скобки, останется N свободных мест.
2. Решить задачу: сколько существует правильных последовательностей из N скобок.

Неверно, т.к.
????(???
==
1. ????()()
или
2. ????(())

[Draeden]

Вот ещё вариант: пусть строка имеет длину N, тогда сделаем массив A размера N x N.
A[l][r] содержит ответ к задаче для подстроки l...r.
Можно заполнять массив, в нём всего N x N элементов.

[Soul]

каким образом предлагаешь заполнять?

[malk]

Считаем ( 1,) -1,? 0.

Используем массив a[n,n/2], где a[i,s]- количество вариантов на i-ом знаке c суммой s.
Если i+1 знак ? то a[i+1,s]:=a[i,s-1]+a[i,s]+a[i,s+1];
Если i+1 знак ( то a[i+1,s]:=a[i,s-1];a[i+1,0]:=0;
Если i+1 знак ) то a[i+1,s]:=a[i,s+1];a[i+1,n/2]:=0;
Результат получается в a[n,0].
Для приведенного выше примера:
\ i 1 2 3 4 5 6
s
3 0 0 1 04 09 21
2 0 1 3 09 12 30
1 1 2 5 12 09 21
0 1 2 4 09 00 09
????()
??()()
?(?)()
(??)()
?()?()
(?)?()
()??()
()()()
(())()

[Soul]

A можно чуть подробнее остановиться на идее, я, если честно, не понял.

[malk]

Считаем знак "(" 1, знак")" -1, знак"?" 0.
a[i,s]- количество вариантов где первые i чисел в сумме дают s.
Будем заполнять массив последовательно a[0,0],a[0,1];a[1,0],a[1,1],a[1,2];...
Ha первом шаге есть один вариант c суммой 0(первый знак "?") и один вариант c суммой 1(первый знак "("). Ha i+1-ом шаге сумму s можно получить в трех случаях: когда на i-ом шаге была сумма s-1,сумма s или сумма s+1.
Если сложить количества вариантов для этих случаев то получим количество вариантов для i+1-ого шага c суммой s. Если встречаем -1 или 1 то количество вариантов равно количество вариантов для i-ого шага c суммой s+1 или s-1. Ha самом последнем шаге (i=n) нас интересует количество вариантов c суммой 0 - то есть где открывающих и закрывающих скобок поровну. Ha всех шагах сумма не должна быть меньше 0 - иначе будет неправильное выражение, где закрывающих скобок слишком много.
Количество правильных вариантов расстановки скобок соответствует числам Каталана, a алгоритм использует метод построения треугольника Каталана.
Можно обойтись двумя массивами a[0..n/2].
Если требуется все знаки "?" превратить в скобки, то алгоритм легко изменить.