Задачи
Скобки
Скобки
Дано выражение, состоящее только из букв a
и знаков операций +
и *
. Напишите программу, вычисляющую количество способов расстановки полного набора скобок в этом выражении таким образом, чтобы каждая пара скобок содержала один знак операции и два операнда, каждый из которых является либо буквой а, либо выражением в скобках. Значение выражения при этом должно остаться прежним, т.е. сначала должны выполняться операции умножения, а затем сложения. Например, для выражения а + а + а * а * а
существует 4 способа расстановки скобок:
(а+(а+(а*(а*а))))
(а+(а+((а*а)*а)))
((а+а)+((а*а)*а))
((а+а)+(а*(а*а)))
Входные данные
В первой строке содержится корректное выражение, содержащее не более 25 знаков операций.
Выходные данные
Вывести количество способов расстановки скобок.
Входные данные #1
a+a+a*a*a
Выходные данные #1
4