"Reverse" Polish
Statement
Goal
This puzzle is a direct continuation of https://www.codingame.com/training/medium/the-polish-dictionaryIn the first puzzle the aim was to get to know reverse polish notation better. But in real life you rarely have to deal with turning rpn to infix notation. Usually it's the other way around.
When you want to create a simple scripting language from scratch, or even just some extended functionality for config files, you'll often run into the issue, that handling infix notation is an expensive task for computers. On the other hand, rpn practically only requires a stack to work.
In this puzzle you're tasked to convert infix notation into rpn. But only having +-*/ as operators is relatively boring, so to throw a wrench into the plan, the unary + and - operators and the ^ (exponentiation) operator is included, alongside parentheses.
For clarity, the operators have the following precedence:
weakest->strongest
+ and -, * and /, unary + and -, ^, and finally ()
Associativity of non unary operators:
Left: + - / *
Right: ^
Operands are either numbers or variables, neither can contain any of the aforementioned operators as a character.
Furthermore, there won't be any set spacing between values, operators, etc.
You don't need to evaluate the expression in the end, and you won't be able to because of the variables.
Input
Line 1: a string S that contains the expression that needs to be turned into rpn.
Output
The resulting rpn expression with a single space separating the operands. The operands should appear in the same order as in the original expression. When the unary + and - operators appear in the answer, prefix them with a @ (@+ and @-)
Constraints
10 ≤ Length of S ≤ 256
1 ≤ Resulting number of rpn operands ≤ 100
There will always be only one possible answer
1 ≤ Resulting number of rpn operands ≤ 100
There will always be only one possible answer
Example
Input
123
Output
123
Tags
Reverse Polish Notation, Stack, Shunting-Yard, Mathematics, interpreter
Difficulty
Hard
Test cases
Simple beginnings Test
Input
123
Output
123
Validator 1 Validator
Input
627
Output
627
One operation Test
Input
3 + 4
Output
3 4 +
Validator 2 Validator
Input
9 * 2
Output
9 2 *
No parentheses yet Test
Input
13 - 42 * 17 + 9
Output
13 42 17 * - 9 +
Validator 3 Validator
Input
42 / 2 + 8 * 7
Output
42 2 / 8 7 * +
Variables Test
Input
apple + 3 * banana
Output
apple 3 banana * +
Validator 4 Validator
Input
cherry - peach / 4
Output
cherry peach 4 / -
Unary operators Test
Input
-13 + +8
Output
13 @- 8 @+ +
Validator 5 Validator
Input
+7 / -4
Output
7 @+ 4 @- /
Exponentiation Test
Input
12^-7 + -3^3
Output
12 7 @- ^ 3 3 ^ @- +
Validator 6 Validator
Input
-7 ^ 9 / 8^-10
Output
7 9 ^ @- 8 10 @- ^ /
Parentheses enter the scene Test
Input
(8 + 4) * 10 ^ (6 + 4)
Output
8 4 + 10 6 4 + ^ *
Validator 7 Validator
Input
(12 / 7)^(42 + 3) * (10 - 10)
Output
12 7 / 42 3 + ^ 10 10 - *
Formatting? What formatting? Test
Input
16- 43+ - 10 * ( 82- 42+x) ^(12 -8)
Output
16 43 - 10 @- 82 42 - x + 12 8 - ^ * +
Validator 8 Validator
Input
apple * 3 ^-2 - 2 ++5 * 2^ ( 20*8)
Output
apple 3 2 @- ^ * 2 - 5 @+ 2 20 8 * ^ * +
Multiple layers of parentheses Test
Input
((3 * -2) / -(8 + 4))
Output
3 2 @- * 8 4 + @- /
Validator 9 Validator
Input
(4 + -16*(6 - 2 + (4 + 8)))
Output
4 16 @- 6 2 - 4 8 + + * +
Left associativity Test
Input
2 ^ x ^ apple ^ tree ^ 8 ^ 3
Output
2 x apple tree 8 3 ^ ^ ^ ^ ^
Validator 10 Validator
Input
1 ^ lemon ^ 9 ^ y ^ f
Output
1 lemon 9 y f ^ ^ ^ ^
Big test Test
Input
Not yet created
Output
~
Validator 11 Validator
Input
Not yet created
Output
~
Solution language
Solution
Stub generator input