Remote Training on Programming

Существует несколько способов записи арифметических выражений. В привычной нам (инфиксной) записи знак операции ставится между аргументами — например: "(10 - 6) * (3 + 5)". В постфиксной (или обратной польской) записи знак операции пишется после аргументов. Например, это же выражение в постфиксной записи будет выглядеть так: "10 6 - 3 5 + *".

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

Вычисление выражения в постфиксной записи выполняется очень просто. Идём слева направо. Встретив знак операции, берём два операнда перед ним, выполняем операцию, стираем её и оба операнда, а на это место записываем результат. Возьмём для примера наше выражение "10 6 - 3 5 + *". На первом шаге выполним вычитание — получится "4 3 5 + *". Теперь выполним сложение — получаем "4 8 *". На последнем шаге выполняем вычитание, и получаем ответ 32.

Представим теперь, что операнды у нас — не короткие числа, а очень длинные (содержащие миллионы цифр). Тогда операции с ними будут выполняться медленно. Пусть наш компьютер выполняет одну операцию за одну секунду. Тогда, чтобы вычислить выражение из примера (но с длинными операндами), ему потребуется три секунды.

Однако, современные компьютеры умеют производить вычисления параллельно! Если в нашем примере операции вычитания и сложения выполнять одновременно, то вычисление выражения займёт всего две секунды вместо трёх. Более формально: любую операцию можно начинать выполнять сразу, как только оба её операнда уже вычислены.

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