ECOO '07 R3 P4 - Reverse Polish Logic

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

Polish mathematician Jan Łukasiewicz (1878-1956) invented a form of symbolic logic that Hewlett Packard implemented in their calculators shortly after his death. It is a method of entering an equation, different from the "algebraic" method we are now familiar with. In honour of Jan, they named the method RPL or Reverse Polish Logic.

In RPL numbers are entered and pushed down on a stack each time you press the Enter key (E in our examples). As soon as you press a binary operation such as + (add), - (subtract), * (times), / (divide), ! (to the power of), that operation is performed on the number in the display and the number on top of the stack. The numbers on the stack are then pushed up one level.

Note that in this problem, ! means "to the power of", as in: 2\ !\ 3 = 8 and 5\ !\ 2 = 25. (The ^ character is a control character in Turing, and cannot be used by those using Turing)

Examples

The expression 45E4+ is algebraically equivalent to 45 + 4 =:

45 enter 45 into the display
E push it on the stack
4 enter 4 into the display
+ add the top of the stack (45) to the display (4)
put 49 in the display

The expression 25E30E12+* is algebraically equivalent to 25 * (30 + 12) =:

25 enter 25 into the display
E push it on the stack
30 enter 30 into the display
E push it on the stack (25 is pushed further down)
12 enter 12 into the display
+ add the top of the stack (30) to the display (12)
put 42 in the display
(25 goes back to the top of the stack)
* multiply top of the stack (25) to the display (42)
put 1050 in the display

The input contains 5 RPL expressions, each on a separate line.

There are no variables, only positive numbers, with or without decimal point and the five operations: +, -, *, /, ! and E. The expressions contain no spaces and are less than 50 characters in length.

Write a program that will translate the expression to its algebraic equivalent form and solve the expression, as in the sample output below. Your answers need not be rounded off, and only use brackets where needed.

Sample Input

56E34E213.7+*678-
1E56E35+16E9-/+
1E3+
13E2!5E2!-
123E

Sample Output

56 * (34 + 213.7) - 678 = 13193.2
1 + (56 + 35) / (16 - 9) = 14
1 + 3 = 4
13 ! 2 - 5 ! 2 = 144
123 = 123

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.