Convert from postfix notation to infix notation This question may not be that creative, but I believe that it is different enough to pose a new challenge.

The Challenge

Your challenge is to write the shortest program possible that can take any valid expression in Reverse Polish Notation and convert it to infix notation that obeys the order of operations and has the necessary parentheses.

Input

Your program will receive a valid RPN expression on STDIN. This expression will consist of numbers and operators. There can be an arbitrary number of spaces between each item, but there will always be a space between two numbers. Likewise, there will never be a space within a number. Here is a formal grammer description, stolen and modified from the linked question above.

expression := expression expression operator | number
operator   := "+" | "-" | "*" | "/" | "^"
number     := digit number | digit
digit      := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"


Here are some simple examples

2 3 -10000 +
16 4    12 3 / * -
1 2 +2 3 +^


In the first example, that is not a negation sign, it is a subtraction operator.

Output

Your program should output an equivalent infix expression to STDOUT, which should be a valid infix expression, with numbers, operators, and parentheses. 

Here is a formal grammer description, again stolen.

expression     := number | subexpression | expression operator expression
subexpression  := "(" expression ")"
operator       := "+" | "-" | "*" | "/"
number         := digit | digit number
digit          := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"


With infix notation, there must be an order of operations and a way to group subexpressions. The order of operations will be this:

Expressions inside parentheses
Exponents right to left
Multiplication and division (of equal importance) left to right
Addition and subtraction (of equal importance) left to right


As an example, 2^3^2-(2^3)^2 should equal 448.

The output should not contain any unneeded parentheses. ((2+1))-1 should reduce to 2+1-1. Also, you should not evaluate any expression. You should also not assume the commutative or associative properties. This means that, while the operators will move around, the numbers will always remain in the same order.

Here are the outputs for the above inputs. Note that what would normally be unneeded parenthesis are in the second example: removing them would invoke the associative property.

2-3+10000
16-4*(12/3)
(1+2)^(2+3)


I will add more examples later.

Rules, Regulations, and Notes

This is code golf, standard rules apply.
Clojure - 282 279 271 268 characters

(dorun(map pr((reduce(fn[s v](let[p '{e 2,* 1,/ 1,+ 0,- 0}[t z](rseq s)a 
#(if(and(seq? %)(&lt;=(p v)(p(nth % 1))))%`(~%))](if(p v)(conj(pop(pop s))
`(~@(a z)~({'e(symbol"^")}v v)~@(a t)))(conj s v))))[](map read-string
(re-seq #"\d+|[e+*/-]"(.replace(read-line)\^\e))))0)))


(line breaks are totally optional, only included for clarity, if removed ensure there is a single space between a and #( between the first two lines. all other spaces between the lines may be removed).

Assumes input will end after the first line, passes the example programs (outputs more spaces sometimes, but the right number of parentheses :)

Program can be tested here: http://ideone.com/gxykA

Ungolfed: 

(defn stackify [s v]
  (let[p '{e 4,* 3,/ 3,+ 2,- 2}
       [t n] (rseq s)
       a #(if (and (coll? %) (&lt;= (p v) (p (nth % 1)))) % `(~%))]
    (if (p v)
      (conj (pop (pop s))
            `(~@(a n) ~({'e(symbol"^")} v v) ~@(a t)))
      (conj s v))))

(defn read-postfix [s]
  "takes a string instead of reading from *in*"
  (-&gt;&gt; (.replace s \^ \e)
       (re-seq #"\d+|[e+*/-]")
       (map read-string)
       (reduce stackify [])
       first
       (map pr)
       dorun))


(woo, first stackexchange post)