## CCC '08 J4 - From Prefix to Postfix

View as PDF

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

Problem type
##### Canadian Computing Competition: 2008 Stage 1, Junior #4

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., , while in prefix notation the operator is positioned before the operands, e.g., . Similarly, the prefix notation for is . 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 is , while the prefix representation of is . 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 is .

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 on a single line. You can assume that each input line contains a valid prefix expression with less than 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 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 -

• commented on May 5, 2020, 4:52 p.m.

i got no clue what this question is asking

• commented on Dec. 19, 2019, 5:22 p.m.

Why there is only one test case, but final score has 100?

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

How about we don't keep on cursing CCC?

(O_O)

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

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

(Ł)

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

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

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

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