Эта задачка была у нас на областной школьников. Мне понравилась тем, что если ее аккуратно проанализировать, то ответ находится в виде очень простой(хотя и рекурсивной) формулы.

Выражение состоит из символов 1, +, -, (, )
Выражение считается правильным (ПВ), если это "1" или "(-ПВ)" или "(ПВ+ПВ)"
Все сотальные выражения считаются неправильными.

Например, (-((1+1)+(-1))) — правильное выражение, -1 -неправильное, (1-1) тоже неправильное.

Дана строка, состоящая из 1, -, +. Найти, сколько в ней различных вариантов расстановки скобок, дающих правильное выражение.