ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1365. Testing Calculator

Time limit: 2.0 second
Memory limit: 64 MB
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 all.
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 expression.
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


  1. To run the existing module, use http://acm.timus.ru/Supplement/CalcEngine/CalcEngineGUI.html
  2. Remember that existing module runs not less than 30 seconds on any set of input data.
  3. You may need to update Java Runtime Engine (JRE) used by your browser. To run the module you need JRE of version 1.3 or higher. The latest version of JRE can be downloaded from here: http://java.sun.com
Problem Author: Aleksandr Klepinin
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005