Parsing/RPN to infix conversion

You are encouraged to solve this task according to the task description, using any language you may know.
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.


class PostfixToInfix {
    static class Expression {
        final static String ops = "-+/*^"
 
        String op, ex
        int precedence = 3
 
        Expression(String e) {
            ex = e
        }
 
        Expression(String e1, String e2, String o) {
            ex = String.format "%s %s %s", e1, o, e2
            op = o
            precedence = (ops.indexOf(o) / 2) as int
        }
 
        @Override
        String toString() {
            return ex
        }
    }
 
    static String postfixToInfix(final String postfix) {
        Stack<Expression> expr = new Stack<>()
 
        for (String token in postfix.split("\\s+")) {
            char c = token.charAt(0)
            int idx = Expression.ops.indexOf(c as int)
            if (idx != -1 && token.length() == 1) {
 
                Expression r = expr.pop()
                Expression l = expr.pop()
 
                int opPrecedence = (idx / 2) as int
 
                if (l.precedence < opPrecedence || (l.precedence == opPrecedence && c == '^' as char))
                    l.ex = '(' + l.ex + ')'
 
                if (r.precedence < opPrecedence || (r.precedence == opPrecedence && c != '^' as char))
                    r.ex = '(' + r.ex + ')'
 
                expr << new Expression(l.ex, r.ex, token)
            } else {
                expr << new Expression(token)
            }
            printf "%s -> %s%n", token, expr
        }
        expr.peek().ex
    }
 
    static void main(String[] args) {
        (["3 4 2 * 1 5 - 2 3 ^ ^ / +", "1 2 + 3 4 + ^ 5 6 + ^"]).each { String e ->
            printf "Postfix : %s%n", e
            printf "Infix : %s%n", postfixToInfix(e)
            println()
        }
    }
}