CCC '08 J4 - From Prefix to Postfix

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Problem type

Prefix notation is a non-conventional notation for writing arithmetic expressions. The standard way of writing arithmetic expressions, also known as infix notation, positions a binary operator between the operands, e.g., 3 + 4, while in prefix notation the operator is positioned before the operands, e.g., +\ 3\ 4. Similarly, the prefix notation for 5 - 2 is -\ 5\ 2. A nice property of prefix expressions with binary operators is that parentheses are not required since there is no ambiguity about the order of operations. For example, the prefix representation of 5 - (4 - 2) is -\ 5 - 4\ 2, while the prefix representation of (5 - 4) - 2 is - - 5\ 4\ 2. The prefix notation is also known as Polish notation, due to Jan Łukasiewicz, a Polish logician, who invented it around 1920.

Similarly, in postfix notation, or reverse Polish notation, the operator is positioned after the operands. For example, postfix representation of the infix expression (5 - 4) - 2 is 5\ 4 - 2\ -.

Your task is to write a program that translates a prefix arithmetic expression into a postfix arithmetic expression.

Input Specification

Each line contains an arithmetic prefix expression. The operators are + and -, and numbers are all single-digit decimal numbers. The operators and numbers are separated by exactly one space with no leading spaces on the line. The end of input is marked by 0 on a single line. You can assume that each input line contains a valid prefix expression with less than 20 operators.

Output Specification

Translate each expression into postfix notation and produce it on a separate line. The numbers and operators are separated by at least one space. The final 0 is not translated.

Sample Input

1
+ 1 2
- 2 2
+ 2 - 2 1
- - 3 + 2 1 9
0

Sample Output

1
1 2 +
2 2 -
2 2 1 - +
3 2 1 + - 9 -

Comments


  • 0
    XTTH  commented on Jan. 9, 2019, 8:22 p.m.

    Ł


  • 1
    xxsc  commented on Nov. 11, 2017, 10:28 a.m.

    How about we don't keep on cursing CCC?

    (O_O)


  • 17
    bobhob314  commented on July 22, 2015, 6:45 a.m.

    Curse you CCC for making me think there was dirt on my screen

    (Ł)


    • 11
      Itachi  commented on April 17, 2016, 10:35 a.m.

      And curse you, bobhob, for making me realize there was dust on my screen.


    • 7
      lKunelk  commented on July 23, 2015, 4:36 p.m.

      hey, you can't curse CCC for spelling his name correctly in Polish...