You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

🔔 Don’t forget to claim the homework on the Homework page!

This assignment focuses on a fundamental concept in computer science: parsing and evaluating mathematical expressions. You will implement the famous Shunting-yard algorithm, to convert expressions from the human-readable infix notation to the more machine-friendly postfix notation (also known as Reverse Polish Notation). This algorithm is a perfect application of the stack data structure. 🧑‍💻

Description

You are given a string representing a mathematical formula in infix notation, with all tokens separated by spaces. Your task is to convert this expression into its equivalent postfix notation.

The expression will consist of:

• Integers: Positive whole numbers.
• Operators: +, -, *, /, ^ (exponentiation).
• Parentheses: (, ).

You must handle operator precedence and associativity correctly:

1. Precedence:
   • ^ has the highest precedence.
   • * and / have medium precedence.
   • + and - have the lowest precedence.
2. Associativity:
   • +, -, *, / are left-associative. For example, 8 - 5 + 3 is treated as (8 - 5) + 3.
   • ^ is right-associative. For example, 2 ^ 3 ^ 2 is treated as 2 ^ (3 ^ 2).
3. Parentheses: () are used for grouping and override the default precedence rules.

Format

Input

Two lines:

1. A single integer $n$ ($1 \leq n \leq 10^5$), the length of the string $s$ (including spaces).
2. A single line containing a string $s$ ($1 \leq |s| \leq 10^5$). The string represents a valid infix mathematical expression where all tokens (numbers, operators, parentheses) are separated by a single space.

Output

Output the corresponding postfix expression on a single line. Each token in the output must be separated by a single space.

Samples

Sample 1

9
3 + 4 * 2

3 4 2 * +

Sample 2

13
( 3 + 4 ) * 2

3 4 + 2 *

Sample 3

13
3 + 2 ^ 3 ^ 2

3 2 3 2 ^ ^ +

Explanation: The exponentiation operator ^ is right-associative, so 2 ^ 3 ^ 2 is evaluated as 2 ^ (3 ^ 2). It also has higher precedence than +.

Sample 4

25
( 5 + 2 ) * ( 8 - 3 ) / 4

5 2 + 8 3 - * 4 /

Sample 5

19
( 123 + 456 ) * 789

123 456 + 789 *

Hints

The test cases are structured to help you build your solution incrementally. We recommend passing the tests in order. 💡

• Test Cases 1-5: Contain only + and - operators, with no parentheses.
• Test Cases 6-10: Contain +, -, *, / operators, with no parentheses. This will test your handling of multiple precedence levels.
• Test Cases 11-20: Contain +, -, *, / operators and parentheses.
• Test Cases 21-30: Contain all operators, including ^, and parentheses. This will test your full implementation, including the right-associative ^ operator.

Limitation

1s, 256MiB for each test case.