P1175 Expression Conversion

The expressions we usually write are called infix expressions because they place the operator between two operands. In many cases, parentheses are necessary to determine the order of operations. Postfix expressions, however, do not require parentheses. Postfix notation: when writing an expression, the operator is written immediately after its two operands. This eliminates the need for parentheses and handles precedence, simplifying the computer’s processing rule to: compute from left to right in order, and replace the operands with the result. For example: `8-(3+2*6)/5+4` can be written as: `8 3 2 6 * + 5 / - 4 +`. The calculation steps are: ``` 8 3 2 6 * + 5 / - 4 + 8 3 12 + 5 / - 4 + 8 15 5 / - 4 + 8 3 - 4 + 5 4 + 9 ``` Write a program to complete this conversion. In the output, leave exactly one space between every token.

A single line containing an infix expression. The input symbols include only these basic symbols: `0123456789+-*/^()`, and formats like `2*-3` will not appear. All numbers in the expression are single-digit; forms like `12` will not appear. Do not perform error checking on the input string.

Several lines of postfix expressions. The $(i + 1)$-th line contains one fewer operator and one fewer operand than the $i$-th line. The last line contains only a single number, which is the result.

The result may be negative, and `/` means integer division. Also, every intermediate value will not exceed $2^{31}$. The string length does not exceed 100. Note that exponentiation `^` is right-associative, i.e., `2 ^ 2 ^ 3` means `2 ^ (2 ^ 3)`, and the postfix form is `2 2 3 ^ ^`. Other operators of the same precedence are left-associative, i.e., `4 / 2 / 2 * 2` means `((4 / 2) / 2) * 2`, and the postfix form is `4 2 / 2 / 2 *`. It is guaranteed that the exponent in exponentiation will not be negative, so all intermediate results are integers. Translated by ChatGPT 5