The Advanced Calculator Machinery (ACM) is going to release a new series of calculators. Like it or not, as a member of ACM, you are asked to develop the software for the new calculator. Here is the detailed technical specification.
The general usage of the calculator is that users input expressions, the calculator computes and displays the final result, or error messages if there is something wrong. The expression is in infix notation and the calculator supports following operators:
People always make mistakes. When user inputs an invalid expression, the calculator should display an error message, telling user that error occurs. There are totally four possible errors:
1. Syntax error: Any kind of syntax error, such as missing operators, redundancy operators and unpaired brackets.
2. Divide by zero: The right operand of operator “/” or “%” is zero.
3. Integer overflow: At any step of the calculation, any intermediate values go beyond the range of 32-bit signed integers.
4. Invalid exponent: The right operand of operator“^” is negative, or both operands are zero (we consider 0^0 undefined).
The calculation works this way: at first the calculator omits all space characters of the expression, check the syntax, and then computes. It always finds the highest priority part of the expression, then operators which combines them, then calculate the result and continue the process, until the final result has been got or error occurs.
For example, for expression 2^3^(-4*5), there are mainly 5 steps (we use brackets to note every part of the expression):
1. Check the syntax, no syntax errors.
2. Fetch the highest priority operator 4, no errors.
3. Do arithmetic -(4), get result -4, no errors.
4. Do arithmetic (-(4))*(5), get result -20, no errors.
5. Because operator “^” has right associativity, we do arithmetic (3)^((-(4))*(5)), e.g. (3)^(-20) first. -20 is a negative number, and negative numbers are not allowed as an exponent, so the calculator simply outputs error message and stops.
Notes: Because “-“ has two meanings, the calculator will treat it as an unary operation at first,
and if it fails, “-“ would be treated as minus operation then.
Write a program to simulate the calculator.
The first line of the input file is an integer T<=200, then following T test cases.
Each test case has only one line, the input expression given to the calculator. Each expression has no more than 2000 characters.
For each test case, output one line contains the case number and the final result or “ERROR!” if any error occurs. See sample for detailed format.
2^(1 2 - 9)^(5%3)
Case 1: 512
Case 2: ERROR!
Case 3: ERROR!
Case 4: -4
Case 5: ERROR!
Case 6: ERROR!