SPOJ.com - Problem POCALC1

POCALC1 - Ancient Pocket Calculator

no tags

Adam likes pocket calculators, especially the early ones. As one of his favorite calculators is about 40 years old, he is not sure how long he will be able to use it. So he had the ingenious idea to develop a simulator that behaves exactly like his calculator. This simulator must be able to read a sequence of keystrokes from the calculator's keypad, process the appropriate calculations and print the calculator's output. As Adam needs only basic arithmetic, the following keys will be sufficient: digits 0 to 9, decimal point, operators +, -, x and : (for division), the equal sign for calculating and displaying a result and the [C] key for reseting the calculator and clearing the display, i.e. the display is set to "0.". Calculations are done from left to right without any operator precedence.

Calculator Display

You may call Adam's calculator a headstrong comtemporary, because of its special behaviour:
There is no invalid sequence of keystrokes. You can press arbitrary keys one after another, the calculator always knows how to handle it. If more than one operator key (including [=]) is pressed directly after another, only the last of these operators will be processed - all previous ones (in that continuous sequence) are ignored.
If more than 8 digit keys are pressed for the input of a single number, only the first 8 digits will be processed - all following digits are ignored. If the actual display value is zero, the typing of the zero key will have no effect, it's just ignored like successive keystrokes of the same operator. If a floating point value is typed in, a leading zero directly before the decimal point may be left out, but will be displayed just the same. If the decimal point key is pressed within a number that already has a decimal point typed in or if the input of a number (as a sequence of digit keys) is terminated by a decimal point, that has no effect.

Input

Input starts with a positive integer t (t<1000) in a single line, the number of testcases. Then t lines follow, each line giving the description of an arbitrary sequence of keystrokes on the calculator's keypad. Every key is enclosed by square brackets, all keystrokes are separated by a single space. The number of keystrokes per sequence is less than 500 and every sequence will be terminated by [=].

Output

For each sequence of keystrokes print the result the calculator will show on the display after the complete sequence of keystrokes has been processed. The size of the display is 8 digits plus an optional "-"-sign in front of the leftmost digit and a decimal point that will always appear, even if the result is an integer value. If a value has more than 8 decimal digits, it has to be rounded to fit into 8 digits. As the calculator's display is filled from right to left, the output has to be adjusted to the right.
If the absolute value of a number rounded to an integer needs more than 8 digits, scientific notation is used. Same case, if the absolute value of a number is larger than 10^-100, but rounding to 8 digits would result in displaying zeros only. If the absolute value is not larger than 10^-100, it results to zero.
In scientific notation a number is expressed as a product of a decimal part and a power of 10. The decimal part has always exactly one non-zero digit before the decimal point, an optional "-" sign in front of the leftmost digit and upto 4 digits after the decimal point, rounded if necessary. If the exponent is negative, a "-" follows, otherwise a space. Then follow two digits representing the exponent; a leading zero is shown in the exponent, if necessary.

Notice that there are two cases, where the calculator will display "Error." instead of showing a result. If a (final or interim) result has a rounded absolute value of at least 10¹⁰⁰ or if you divide by zero. After an error has occured, all following keystrokes are ignored unless [C] is pressed.

For more clarity of the calculator's behaviour and the required input and output format please look at the examples below.

Example

Input:
12
[3] [+] [4] [x] [5] [=]
[1] [:] [6] [=]
[4] [.] [8] [-] [x] [+] [-] [+] [x] [-] [.] [=]
[4] [.] [8] [-] [x] [+] [-] [+] [x] [.] [=]
[+] [+] [+] [+] [+] [+] [1] [=] [=] [=]
[9] [8] [C] [-] [7] [6] [5] [4] [3] [2] [1] [0] [1] [2] [3] [4] [=]
[1] [=] [2] [=] [3] [=]
[5] [:] [9] [8] [7] [8] [9] [8] [9] [8] [7] [8] [8] [:] [4] [5] [6] [7] [8] [9] [=]
[-] [9] [9] [9] [9] [9] [9] [9] [9] [-] [-] [-] [-] [8] [8] [8] [8] [8] [8] [=]
[2] [.] [3] [.] [4] [.] [5] [=]
[0] [0] [0] [0] [0] [=]
[.] [:] [.] [=]
 
Output:
       35.
 0.1666667
       4.8
        0.
        1.
-76543210.
        3.
  1.108-13
-1.0089 08
     2.345
        0.
    Error.

Submit solution!

hide comments

< Previous 1 2 3 4 5 Next >

	numerix: 2014-10-08 07:52:14 @S.Y.P.Lai: I sent a PM to you.
	S.Y.P.Lai: 2014-10-08 06:55:53 @Min_25 Thank you! Let me see whether I can use the same settings as yours. I used 3 formatting strings: "% 11.4E" for Sci.Not. "% 10.7f" for (+/-)0.XXXXXXX (tailing zero removed) "% 9.f" for (+/-)1 <= result < (+/-)99999999.5 (digit after decimal point varies accordingly) Edit: I found my formatting strings have same effect as yours. The extra "length" in my formatting strings have no effect to the result. Now, I am thinking that there may be some other hard to discover problems not related to rounding and precision. Last edit: 2014-10-08 07:44:14*
	Min_25: 2014-10-08 06:47:27 @S.Y.P.Lai I used the "%6.4e" and "%9.f" format strings for rounding and did not use a round function. The results of these inputs are the same as the results of the evaluation of them. For example, the output of "[1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [4] [5] [:] [1] [0] [=] " will be 12345.674 because (123456 + 0.745) / 10 is evaluated as 12345.67449999... . EDIT: I used "%6.4e" for the scientific notation and "%9.f" otherwise. Last edit: 2014-10-08 07:25:38
	S.Y.P.Lai: 2014-10-08 03:57:11 @numerix Thank you for the hint. The problem of [1] [4] [0] [1] [4] [:] [3] [2] [-] [7] [0] [0] [3] [5] [.] [1] [7] [=] is not caused by the rounding at the end. It is the internal precision problem. I have changed the input code to increase float point accuracy. It looks like that specific value can now be rounded to -69597.232 instead of -69597.233 My code still gets WA. Is there any other problem you can let me know? @Min_25 Thank you for the additional info. Could you let me know more about which rounding method you are using? I used sprintf() and round(). For tie breaks, sprintf() will produce irregular results; round() will always round away from zero. I also tried manually "round half to even", but it gets WA. According to Mitch, "round half to even" is used only for values stored exactly in double. Could you try the following calculation and post the result here? [0] [.] [0] [0] [0] [0] [0] [0] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [1] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [2] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [3] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [4] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [5] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [6] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [7] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [8] [5] [:] [1] [0] [=] [0] [.] [0] [0] [0] [0] [0] [9] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [0] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [1] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [2] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [3] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [4] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [5] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [6] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [7] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [8] [5] [:] [1] [0] [=] [-] [0] [.] [0] [0] [0] [0] [0] [9] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [0] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [1] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [2] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [3] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [4] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [5] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [6] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [7] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [8] [5] [:] [1] [0] [=] [1] [2] [3] [4] [5] [6] [+] [0] [.] [7] [9] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [0] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [1] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [2] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [3] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [4] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [5] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [6] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [7] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [8] [5] [:] [1] [0] [=] [-] [1] [2] [3] [4] [5] [6] [-] [0] [.] [7] [9] [5] [:] [1] [0] [=] Last edit: 2014-10-08 07:57:17
	numerix: 2014-10-07 23:09:19 @S.Y.P.Lai: Check the following example. [1] [4] [0] [1] [4] [:] [3] [2] [-] [7] [0] [0] [3] [5] [.] [1] [7] [=]
	S.Y.P.Lai: 2014-10-07 22:32:46 congratulation @ Min_25 My code passed all the test cases I found, but the result is always WA. I was using long long integer for both mantissa and the exponent in my first version. Now, I've rewritten all the code to use double, but the result is the same. I cannot continue until numerix come back and give me some hint.
	Min_25: 2014-10-07 18:01:43 The comments, forum and randomly-generated test cases helped me a lot. Apparently there are no test cases whose result satisfies 0 < abs(result) < 9.99995e-100. EDIT: @S.Y.P.Lai Thank you. I stored the number using double and rounded it using a format string as it had been mentioned by Mitch. As far as I checked, it seems that we don't need to take care of the corner cases such as 99999999.5, 0.00000005, 9.99995e99 and so on, seriously. And calculating [0] [.] [1] [2] [3] [4] [5] [6] [7] [=] as 0.1 + 0.02 + ... + 0.0000007 did not affect the results (of the test cases), which often has more errors than calculating it as 1234567 / 1e7. Last edit: 2014-10-08 06:04:43
	S.Y.P.Lai: 2014-10-07 04:16:05 @Mitch Schwartz Thank you for the information. The key point is that I should use standard rounding of double, instead of "round towards positive infinity" for tie break. I wrote too much code to manually handle the rounding. I store the mantissa and the exponent separately and combine them only when displaying results. That's why I cannot get the same rounding behaviour of "double". I will modify the code to store values on double.
	Mitch Schwartz: 2014-10-07 01:31:34 @S.Y.P.Lai: I've replied to your post on the forum. Also, you should display "Error." if and only if there is an internal error state. Last edit: 2014-10-07 03:26:49
	S.Y.P.Lai: 2014-10-01 02:46:47 @numerix Are you still looking after this problem? How far is my code from being AC? (both time and correctness) Could you give me some hint? For 0.0000095:10=, should I display it as 0.000001 or 0.0000010 ? If tailing zeros are needed for rounded numbers, advanced rounding code may be needed. For 0.0000005:10=, it should display "0.0000001", and for -0.0000005:10=, it should display "-5.-08", right? "1.0001-100" is greater than 10^-100, so it will not be rounded to zero and will be displayed on screen using one more digit, right? 9.99995E+99 will not cause error when displayed as "1. 100", right? ".12345678x10=" will get "1.234567" only, the "free zero" will be counted as the first digit input, right? 0.005+123456.78=, it returns 123456.79, but if there is a next step, it will keep 123456.785 in memory. i.e. 0.005+123456.78-100000=, it will return 23456.785. Am I right? If the answer to the above question is yes, how many "internal digits" should I keep? AFAIK, the 38 years old TI-30 can only store 11 digits inside register. I can keep 16 digits in base 10 with "double" in C++, but it may become the cause of WA. For example, my code gets "0.7142857" for the input 5/7-.714285x1000000=, and it can get back the whole 0.1234567 from input 12345678+0.1234567-12345678= Please check my submission 12527115 when you are back. I've set the following options in code: + tailing zeros, even with significance, will be dropped (like the example result 1.108-13, internal value is 1.1080053E+13.) + the free zero before [.] uses up one digit + up to 17 internal digits (double) are stored + 1.0001E-100 will be displayed as 0. in output but not being rounded to zero internally + 9.99995E+99 will be displayed as Error. in output but not causing error internally Thank you! Last edit: 2014-10-03 08:10:43

Submit solution!

Added by:	numerix
Date:	2011-03-06
Time limit:	0.200s
Source limit:	10000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	own problem