|
Темы:
Expression parsing
A second grade student was told the rules of how to perform arithmetic operations in order to calculate the value of an arithmetic expression consisting of numbers, brackets, and signs of arithmetic operations + (addition) and * (multiplication). After that, he was given exercises — several tasks in which you want to arrange the order in which actions are performed. Help him.
The rules for calculating the expression, told to the student, sound like this. If there are no parentheses in the expression, then all multiplication operations from left to right are performed first, and then — addition operations also from left to right. If the expression contains brackets, then the leftmost pair of brackets (opening and closing) is found, containing a bracketless expression inside itself, which can be calculated according to the rules described above. Further, this expression (together with brackets) is mentally removed from the expression and replaced by the number – result. If there are brackets left in the expression, then the procedure is repeated.
Write a program that, for a correct expression, will determine the order in which arithmetic operations are performed. Since the numbers themselves in this problem will not be essential for us, we will replace them with signs #.
Input
The input file contains one line consisting of the characters #, +, *, (, ). The string length does not exceed 250 characters. The string matches a valid arithmetic expression.
Imprint
Output the same string to the output file, replacing the operation signs + and * in it with natural numbers that specify the order in which actions are performed in accordance with the described rules.
Examples
| # |
Input |
Output |
| 1 |
#+#*# |
#2#1# |
| 2 |
#+#+(#+#) |
#2#3(#1#) |
| 3 |
#+(#+#*#)*#+# |
#4(#2#1#)3#5# |
| 4 |
#+#+#+#+#+#+#+#+#+#+# |
#1#2#3#4#5#6#7#8#9#10# |
| 5 |
#+#+(#+(#+#))+(#+#) |
#4#5(#2(#1#))6(#3#) |
|