Solutions that minimize parentheses must work with the following test 
case:
"3 5 * 5 8 * /" should turn into "3 * 5 / (5 * 8)" not "3 * 5 / 5 * 8"
similarly for
"3 5 + 5 8 + -" which should turn into "3 + 5 - (5 + 8)"

Most of the solutions posted so far get this wrong (I haven't checked 
exhaustively). A few that notably get it correct (while in some way 
minimzing parentheses):
* Daniel Martin
* Robert Dober

--Ken

-- 
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/