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.


procedure main()  
every rpn := ![       
   "3 4 2 * 1 5 - 2 3 ^ ^ / +",  # reqd
   "1 2 + 3 4 + 5 6 + ^ ^",  
   "1 2 + 3 4 + 5 6 + ^ ^",
   "1 2 + 3 4 + ^ 5 6 + ^"       # reqd
   ] do {
      printf("\nRPN   = %i\n",rpn)
      printf("infix = %i\n",RPN2Infix(rpn,show))
      show := 1 # turn off inner working display
      }
end
 
link printf
 
procedure RPN2Infix(expr,show)            #: RPN to Infix conversion
static oi
initial {
   oi := table([9,"'"])                   # precedence & associativity  
   every oi[!"+-"]   := [2,"l"]             # 2L
   every oi[!"*/"]   := [3,"l"]             # 3L
   oi["^"]           := [4,"r"]             # 4R
   }
 
   show := if /show then printf else 1    # to show inner workings or not
   stack := []
   expr ? until pos(0) do {               # Reformat as a tree
      tab(many(' '))                         # consume previous seperator
      token := tab(upto(' ')|0)              # get token
      if token := numeric(token) then {      # ... numeric
         push(stack,oi[token]|||[token])                   
         show("pushed numeric   %i : %s\n",token,list2string(stack))
         }
      else {                                 # ... operator
         every b|a := pop(stack)             # pop & reverse operands
         pr := oi[token,1]
         as := oi[token,2]
         if a[1] < pr | (a[1] = pr & oi[token,2] == "r") then        
            a[3] := sprintf("( %s )",a[3]) 
         if b[1] < pr | (b[1] == pr & oi[token,2] == "l") then  
            b[3] := sprintf("( %s )",b[3]) 
         s := sprintf("%s %s %s",a[3],token,b[3])         
         push(stack,[pr,as,s])               # stack [prec, assoc, expr]
         show("applied operator %s : %s\n",token,list2string(stack))
         }
   }
 
   if *stack ~= 1 then stop("Parser failure") 
   return stack[1,3]
end
 
procedure list2string(L)                  #: format list as a string
   s := "[ " 
   every x := !L do 
      s ||:= ( if type(x) == "list" then list2string(x) 
               else x) || " "    
   return s || "]"
end