Задача H. Раскрытие скобок

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Исходная строка, содержащая некоторое арифметическое выражение, состоит из набора символьных идентификаторов (выступающих в роли операндов), знаков операций ('+', '-', '*') и круглых скобок. Между ними также допускается наличие разделителей из произвольного числа пробелов. При этом знак минуса может обозначать как бинарную, так и унарную операцию. Между любыми двумя знаками операций всегда присутствуют либо скобки, либо операнды. Для записи операндов здесь используются строчные буквы латинского алфавита.

В указанном выражении требуется раскрыть скобки и выполнить приведение подобных слагаемых. На выходе каждое такое слагаемое должно быть записано в следующем формате:

C * A[1]^p[1] * A[2]^p[2] * ... * A[26]^p[26],

где C — некоторый целочисленный коэффициент (может быть опущен, если он равен единице);
A[i] — множитель, соответствующий i-му символу алфавита;
p[i] — целое число, определяющее его степень.

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

Формат входного файла

Входной файл "input.txt" содержит единственную строку с арифметическим выражением.

Формат выходного файла

Выходной файл "output.txt" должен содержать все полученные слагаемые, приведенные к требуемому виду и разделенные символами '+' либо '-'
(в зависимости от знаков стоящих перед ними коэффициентов).

Если полученное выражение тождественно равно нулю, в выходной файл выводится единственное число 0.

Ограничения

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

Число открывающихся скобок ограничено и не превосходит 20.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
- a * b * (b+a) +b*c + b*(a + c)
2*b*c+a*b-a*b^2-a^2*b
2
 (a + b) - b -(a - b) -b 
0

0.104s 0.022s 15