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.


 
;;;; Parsing/RPN to infix conversion
(defstruct (node (:print-function print-node)) opr infix)
(defun print-node (node stream depth)
  (format stream "opr:=~A infix:=\"~A\"" (node-opr node) (node-infix node)))
 
(defconstant OPERATORS '((#\^ . 4) (#\* . 3) (#\/ . 3) (#\+ . 2) (#\- . 2)))
 
;;; (char,char[,boolean])->boolean
(defun higher-p (opp opc &optional (left-node-p nil))
  (or (> (cdr (assoc opp OPERATORS)) (cdr (assoc opc OPERATORS)))
      (and left-node-p (char= opp #\^) (char= opc #\^))))
 
;;; string->list
(defun string-split (expr)
  (let ((p (position #\Space expr)))
    (if (null p) (list expr)
        (append (list (subseq expr 0 p))
                (string-split (subseq expr (1+ p)))))))
 
;;; string->string
(defun parse (expr)
  (let ((stack '()))
    (format t "TOKEN   STACK~%")
    (dolist (tok (string-split expr))
      (if (assoc (char tok 0) OPERATORS) ; operator?
          (push (make-node :opr (char tok 0) :infix (infix (char tok 0) (pop stack) (pop stack))) stack)
          (push tok stack))
 
      ;; print stack at each token
      (format t "~3,A" tok)
      (dotimes (i (length stack)) (format t "~8,T[~D] ~A~%" i (nth i stack))))
 
    ;; print final infix expression
    (if (= (length stack) 1)
        (format nil "~A" (node-infix (first stack))) 
        (format nil "syntax error in ~A" expr))))
 
;;; (char,node,node)->string
(defun infix (operator rightn leftn)
 
  ;; (char,node[,boolean]->string
  (defun string-node (operator anode &optional (left-node-p nil))
    (if (stringp anode) anode
        (if (higher-p operator (node-opr anode) left-node-p)
            (format nil "( ~A )" (node-infix anode)) (node-infix anode))))
 
  (concatenate 'string
               (string-node operator leftn t)
               (format nil " ~A " operator)
               (string-node operator rightn)))
 
;;; nil->[printed infix expressions]
(defun main ()
  (let ((expressions '("3 4 2 * 1 5 - 2 3 ^ ^ / +"
                       "1 2 + 3 4 + ^ 5 6 + ^"
                       "3 4 ^ 2 9 ^ ^ 2 5 ^ ^")))
    (dolist (expr expressions)
      (format t "~%Parsing:\"~A\"~%" expr)
      (format t "RPN:\"~A\" INFIX:\"~A\"~%" expr (parse expr)))))
 