Здравствуйте, leaf, Вы писали:

L>По сути это задача из задачника Лаврова и Максимовой по мат. логике
L>(часть 2, параграф 1, задача 2 (страница 52))

L>-- можно записать и короче, применив функции высшего порядка,
L>-- но это первое, что пришло в голову.
<>
prolog? refal?

L>Предлагаю народу усложненный вариант задачи: нужно найти её нерекурсивную форму.
L>Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями
L>нерекурсивной формы вообще не существует).

Первое. Унарное отрицание не влияет на количество скобок.
(можно, я не буду доказывать?)
Следовательно, достаточно выбросить все знаки "-", убедившись только, что в строке не было последовательностей "-+" и "-." (где "." — конец строки).

Второе. Убедиться, что получилась строка "1" [{ "+" "1" }]
Число расстановок скобок для нее — это функция от количества цифр|плюсов.

1 == 1 === 1
11 == (11) === 1
111 == (11)1, 1(11) === 2
1111 == (111)1, 1(111), (11)(11) === 2+2+1 == 5
11111 == (1111)1, (111)(11), (11)(111), 1(1111) === 5+2+2+5 == 14
111111 == (11111)1, (1111)(11), (111)(111), (11)(1111), 1(11111) == 14+5+2*2+5+14 == 42

Эта последовательность (1,1,2,5,14,42...) -- числа Каталана.
http://www.combinatorics.by.ru/katalan.htm
K[1] = 1
K[n] = K[1]K[n-1] + K[2]K[n-2] + ... + K[n-2]K[2] + K[n-1]K[1]

K[n] = (4n-2)!!!!/(n+1)!
(где !!!! — обобщенный факториал: n!!!! = 1*(1+4)*(1+4*2)*(1+4*3)*...*n', n' <= n)

Очевидно, есть простой итерационный способ вычислить это значение.