Thursday. April 21. First round of IX Urals Programming Contest Championship has just finished. All
teams left the contest area and went to celebrate results of the first round, make sightseeing tour around
Ekaterinburg, or just have a little rest after competition.
Jury would like to have a rest too, but it is impossible. It turned out, that one task for the second round
is missing. Moreover, the error in contest management system was discovered. No, it is not a critical bug,
which distorts results, but a very annoying mistake: one module of the contest management system makes
processing of each submission longer by at least 30 seconds.
Some investigations were done. It was found, that nobody knows what this module is intended for. With
this module contest management system works very slowly. But without the module it does not work at
It seems, that there is no problem. One may take module sources, read them, find specifications for the
module, resolve the error, compile the module and put the corrected version into the system. Unfortunately,
the module was written 8 years ago when The First Urals Programming Contest was prepared and now
sources are not available. They are just lost. Jury feels lost too.
Eureka! We can give out the module to participants of the contest! They are clever enough to run it,
discover the logic and write another version of the module, which will run without delay. Moreover, it is
an excellent task for the second round!
Jury was able to discover some information about the module. It is known that the module reads input
data from the input stream. Each line of the input contains single arithmetic expression, which is
evaluated by module. Each expression consists of arithmetic operations of addition (+), multiplication
(*), integer division (/) and concatenation.
Arithmetic operations are written in prefix form with unlimited number of operands. This way expression
"+3;6;10" has a result of "19". Operation of concatenation does not have any notation and gets executed
when no other operation is given. This way expression "3;6;9" is evaluated to "369". It is known also
that expressions may contain brackets. For example, expression "(+3;6)(*2;3)" has a result of "96". It
may be assumed that logic of expression evaluation does not depend on context. It means, that each
subexpression is always evaluated in the same way with no dependency on it's entrance into the whole
Nothing more is known about the module. You see, that there is no information on how arithmetic
operations interact with concatenation, brackets and separator character (;). You have to discover it by
yourself. To do it, you will be given an existing module. You have to run it, investigate the logic and
reproduce it in your solution.
Input data will be located in the input stream. Each line should be interpreted as a separate expression.
Expression will consist of the following characters only: "0123456789+*/();".
You may assume, that all intermediate values and result of expression evaluation are in the range from 0
to 109. You may also assume that there will be no expressions longer than 50 characters.
Your solution must reproduce the logic of the given module. It should produce output stream with the result of evaluation of expresions from the input. Each line of output must be of
the following form: "Expression evaluates to: ", where is the line
number and is the result of evaluation of expression in the line of the input stream.
Expression 1 evaluates to: 96
Expression 2 evaluates to: 91
Problem Author: Aleksandr Klepinin
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005