Ученику второго класса рассказали правила, как нужно выполнять арифметические действия, чтобы вычислить значение арифметического выражения, состоящего из чисел, скобок и знаков арифметических операций + (сложение) и * (умножение). После этого ему дали упражнения — несколько задач, в которых требуется расставить порядок выполнения действий. Помогите ему.
Правила вычисления выражения, рассказанные ученику, звучат так. Если в выражении вообще нет скобок, то сначала выполняются все операции умножения слева направо, а затем — операции сложения также слева направо. Если же в выражении есть скобки, то находится самая левая закрывающая скобка и соответствующая ей открывающая. Выражение между ними не содержит скобок и может быть вычислено по вышеописанным правилам. Дальше это выражение (вместе со скобками) мысленно удаляется из выражения и заменяется числом – результатом. Если в выражении остались скобки, то процедура повторяется.
Напишите программу, которая для корректного выражения будет определять порядок выполнения арифметических действий. Поскольку сами числа в этой задаче нам будут не существенны, мы заменим их на знаки #.
Во входном файле записана одна строка, состоящая из символов #, +, *, (, ). Длина строки не превышает 250 символов. Строка соответствует правильному арифметическому выражению.
В выходной файл нужно вывести ту же строку, заменив знаки операций + и * в ней натуральными числами, задающими порядок выполнения действий в соответствии с описанными правилами.
#+#*#
#2#1#
#+#+(#+#)
#2#3(#1#)
#+(#+#*#)*#+#
#4(#2#1#)3#5#
#+#+#+#+#+#+#+#+#+#+#
#1#2#3#4#5#6#7#8#9#10#
#+#+(#+(#+#))+(#+#)
#4#5(#2(#1#))6(#3#)