[CCC 2008 J4] From Prefix to Postfix

Luogu

IDLGP9857

Time1000ms

Memory128MB

DifficultyP2

2008CCC（加拿大）

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. ## Input 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 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. [samples]

Samples

Input #1

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

Output #1

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

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2008 J4] From Prefix to Postfix",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9857"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments