题目描述

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, orreverse 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.

输入格式

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.

输出格式

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.

题目大意

给定一个前缀表达式，请你将其转换为一个逆波兰表示法。

每个表达式运算符个数小于等于 $20$。

以下是前缀表达式和逆波兰表达式的范例：

在书写正常算式 $(5 - 4) - 2$ 时，如果要将其改成前缀表达式，就是 $-$ $-$ $5$ $4$ $2$，而改写成逆波兰表达式，就是 $5$ $4$ $-$ $2$ $-$。

注意本题有多组数据，每次当你读入到 $0$ 时，视为结束程序。

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 -