Четверг. 21 апреля 2005 г. Закончился первый тур IX Чемпионата Урала по программированию. Все участники ушли отмечать начало чемпионата, наслаждаться видами Екатеринбурга, да и просто отдыхать после напряженного соревнования.

А вот жюри не до отдыха. Оказалось, что для второго тура не хватает одной задачи. К тому же в проверяющей системе обнаружена ошибка. Вернее не ошибка, - но довольно досадное недоразумение: обнаружен модуль проверяющей системы, задерживающий обработку каждого решения не менее, чем на 30 секунд.

После некоторого исследования было выяснено, что обнаруженный модуль имеет непонятное назначение. Чем он занимается, никто не знает, но без него система не работает. А с ним работает медленно.

Казалось бы, какие проблемы? Достали исходники, разобрались, зачем модуль нужен, исправили ошибку, откомпилировали - и все работает без каких-либо задержек. Но не тут то было. Выяснилось, то данный модуль был написан 8 лет назад, к первому Чемпионату Урала, и его исходные коды за это время успели потеряться. Жюри в унынии...

Эврика! Дадим участникам наш модуль. Они позапускают его, - и поймут как он работает. После этого им не составит труда написать такой-же, но работающий без задержек. Заодно и нехватку задач устраним. На том и порешили!

Жюри удалось вспомнить некотороую информацию о работе модуля. Известно, что каждая строка его входных данных описывает некоторое арифметическое выражение, значение которого и считает модуль. Каждое выражение состоит из арифметических операций сложения (+), умножения (*), целочисленного деления (/) и операции конкатенации.

Арифметические операции записываются в префиксной форме с неограниченным числом аргументов. То есть выражение "+3;6;10" даст результат "19". Операция конкатенации не имеет обозначения и выполняется тогда, когда иных операций не указано. Так выражение "3;6;9" даст результат "369". Также известно, что в выражениях можно использовать скобки. Поэтому выражение "(+3;6)(*2;3)" дает в результате "96". Можно предполагать, что логика обработки выражений не зависит от контекста. То есть любое выражение будет вычисляться всегда одинаково вне зависимости от его вхождения в большее выражение.

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

Входные данные поступают из входного потока. Каждая строка должна считаться независимым выражением. Выражения могут содержать лишь следующие символы: "0123456789+*/();".

Можно предполагать, что все промежуточные значения и результат вычисления выражения лежат в диапазоне от 0 до 10⁹. Также можно предполагать, что на входе не будет выражений, содержащих более чем 50 символов.

Выше решение должно воспроизводить логику существующего модуля. Оно должно выдавать в выходной поток результаты вычисления выражений, полученных на входе. Каждая строка результата должна иметь следующий вид: "Expression evaluates to: ", где - это номер строки и - это результат вычисления выражения, находящегося в строке входного набора данных.