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.


with javascript_semantics
bool show_workings = true
 
constant operators  = {"^","*","/","+","-"},
         precedence = { 4,  3,  3,  2,  2 },
         rassoc     = {'r', 0 ,'l', 0 ,'l'}
 
procedure parseRPN(string expr, expected)
    sequence stack = {},
             ops = split(expr)
    string lhs, rhs
    integer lprec,rprec
    printf(1,"Postfix input: %-32s%s", {expr,iff(show_workings?'\n':' ')})
    if length(ops)=0 then ?"error" return end if
    for i=1 to length(ops) do
        string op = ops[i]
        integer k = find(op,operators)
        if k=0 then
            stack = append(stack,{9,op})
        else
            if length(stack)<2 then ?"error" return end if
            {rprec,rhs} = stack[$]; stack = stack[1..$-1]
            {lprec,lhs} = stack[$]
            integer prec = precedence[k]
            integer assoc = rassoc[k]
            if lprec<prec or (lprec=prec and assoc='r') then
                lhs = "("&lhs&")"
            end if
            if rprec<prec or (rprec=prec and assoc='l') then
                rhs = "("&rhs&")"
            end if
            stack[$] = {prec,lhs&" "&op&" "&rhs}
        end if
        if show_workings then
            ?{op,stack}
        end if
    end for
    string res = stack[1][2]
    printf(1,"Infix result: %s [%s]\n", {res,iff(res=expected?"ok","**ERROR**")})
end procedure
 
parseRPN("3 4 2 * 1 5 - 2 3 ^ ^ / +","3 + 4 * 2 / (1 - 5) ^ 2 ^ 3")
show_workings = false
parseRPN("1 2 + 3 4 + ^ 5 6 + ^","((1 + 2) ^ (3 + 4)) ^ (5 + 6)")
parseRPN("1 2 + 3 4 + 5 6 + ^ ^","(1 + 2) ^ (3 + 4) ^ (5 + 6)")
parseRPN("moon stars mud + * fire soup * ^","(moon * (stars + mud)) ^ (fire * soup)")
parseRPN("3 4 ^ 2 9 ^ ^ 2 5 ^ ^","((3 ^ 4) ^ 2 ^ 9) ^ 2 ^ 5")
parseRPN("5 6 * * + +","error")
parseRPN("","error")
parseRPN("1 4 + 5 3 + 2 3 * * *","(1 + 4) * (5 + 3) * 2 * 3")
parseRPN("1 2 * 3 4 * *","1 * 2 * 3 * 4")
parseRPN("1 2 + 3 4 + +","1 + 2 + 3 + 4")
parseRPN("1 2 + 3 4 + ^","(1 + 2) ^ (3 + 4)")
parseRPN("5 6 ^ 7 ^","(5 ^ 6) ^ 7")
parseRPN("5 4 3 2 ^ ^ ^","5 ^ 4 ^ 3 ^ 2")
parseRPN("1 2 3 + +","1 + 2 + 3")
parseRPN("1 2 + 3 +","1 + 2 + 3")
parseRPN("1 2 3 ^ ^","1 ^ 2 ^ 3")
parseRPN("1 2 ^ 3 ^","(1 ^ 2) ^ 3")
parseRPN("1 1 - 3 +","1 - 1 + 3")
parseRPN("3 1 1 - +","3 + 1 - 1")           -- [txr says 3 + (1 - 1)]
parseRPN("1 2 3 + -","1 - (2 + 3)")
parseRPN("4 3 2 + +","4 + 3 + 2")
parseRPN("5 4 3 2 + + +","5 + 4 + 3 + 2")
parseRPN("5 4 3 2 * * *","5 * 4 * 3 * 2")
parseRPN("5 4 3 2 + - +","5 + 4 - (3 + 2)") -- [python says 5 + (4 - (3 + 2))]
parseRPN("3 4 5 * -","3 - 4 * 5")
parseRPN("3 4 5 - *","3 * (4 - 5)")         -- [python says (3 - 4) * 5] [!!flagged!!]
parseRPN("3 4 - 5 *","(3 - 4) * 5")
parseRPN("4 2 * 1 5 - +","4 * 2 + 1 - 5")   -- [python says 4 * 2 + (1 - 5)]
parseRPN("4 2 * 1 5 - 2 ^ /","4 * 2 / (1 - 5) ^ 2")
parseRPN("3 4 2 * 1 5 - 2 3 ^ ^ / +","3 + 4 * 2 / (1 - 5) ^ 2 ^ 3")
