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.
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.
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.
1 + 1 2 - 2 2 + 2 - 2 1 - - 3 + 2 1 9 0
1 1 2 + 2 2 - 2 2 1 - + 3 2 1 + - 9 -