user
This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

Task

Create a program that takes an RPN representation of an expression formatted as a space separated sequence of tokens and generates the equivalent expression in infix notation.

* Assume an input of a correct, space separated, string of tokens
* Generate a space separated output string representing the same expression in infix notation
* Show how the major datastructure of your algorithm changes with each new token parsed.
* Test with the following input RPN strings then print and display the output here.

:   :   :   :   :   | RPN input | sample output |
                    | --- | --- |
                    | `3 4 2 * 1 5 - 2 3 ^ ^ / +` | `3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3` |
                    | `1 2 + 3 4 + ^ 5 6 + ^` | `( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )` |

* Operator precedence and operator associativity is given in this table:

:   :   :   :   :   :   :   :   | operator | precedence | associativity | operation |
                                | --- | --- | --- | --- |
                                | ^ | 4 | right | exponentiation |
                                | \* | 3 | left | multiplication |
                                | / | 3 | left | division |
                                | + | 2 | left | addition |
                                | - | 2 | left | subtraction |

See also

* Parsing/Shunting-yard algorithm   for a method of generating an RPN from an infix expression.
* Parsing/RPN calculator algorithm   for a method of calculating a final value from this output RPN expression.
* Postfix to infix   from the RubyQuiz site.
assistant
(formerly Perl 6)

```
sub p ($pair, $prec) { $pair.key < $prec ?? "( {$pair.value} )" !! $pair.value }

sub rpm-to-infix($string) {
    my @stack;
    for $string.words {
        when /\d/      { @stack.push: 9 => $_ }
        my ($y,$x) = @stack.pop, @stack.pop;
        when '^'       { @stack.push: 4 => ~(p($x,5), $_, p($y,4)) }
        when '*' | '/' { @stack.push: 3 => ~(p($x,3), $_, p($y,3)) }
        when '+' | '-' { @stack.push: 2 => ~(p($x,2), $_, p($y,2)) }
    }
    ($string, @stack».value).join("\n") ~ "\n";
}

say rpm-to-infix $_ for
    '3 4 2 * 1 5 - 2 3 ^ ^ / +',
    '1 2 + 3 4 + ^ 5 6 + ^';

```

Output:

```
3 4 2 * 1 5 - 2 3 ^ ^ / +
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

1 2 + 3 4 + ^ 5 6 + ^
( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
```