beecrowd | 1741

Reversed John’s Notation

By Contest Road to Fortaleza VII BR Brazil

Timelimit: 3

Little John is learning how to solve arithmetic expressions. But conventional expressions are too boring to him. Because of that, his father is teaching him how to solve expressions written in different forms. The first non-traditional form he learned was the Reverse Polish Notation, a form of writing expressions that interestingly does not need parenthesis. John has a keen interest in RPN expressions, but he thinks he can create his own notation that is even more interesting. That’s why he created the Reversed John’s Notation (RJN).

John came up with the following recursive definition of a valid RJN expression:

John now amuses himself writing and solving expressions in the RJN form. As he’s a natural adventurous kid, he likes bigger expressions the most. However, sometimes this innocent boy runs into trouble. Part of the expressions he writes are apparently unsolvable, because they seem malformed, and some other expressions cause divisions by zero. But when he solves big expressions for the second time, he generally gets different results.

He would like to know for sure the result of the expressions he writes. Because you really like John, you decided to write a program to help him.


The input consists of several test cases. Each test case is a line with n characters (1 ≤ n ≤ 2×106) that could possibly form an expression in the RJN form. This expression contains only digits from 0 to 9 and the mentioned operators separated by a single space.

The input terminates in the end of the input file.


For each test case, print one single line, with the following form:

“The answer is N.” if the expression is valid and can be solved and its result is N.

“Division by zero.” if the expression is syntatically valid, but in the process of solving it, one tries to divide by zero.

“Invalid expression.” if the expression can’t be solved as a RJN expression.

All the results, both final and intermediate, will fit in a signed 32-bit integer.

Sample Input Sample Output

+ 2 2
- 5 * 2 * 7 8
/ 2 0
/ 0 2
2 3 +

The answer is 4.
The answer is 107.
The answer is 0.
Division by zero.
Invalid expression.