What is the inversion of the Shunting Yard algorithm?

Question

Dijkstra's Shunting Yard algorithm is used to parse an infix notation and generate RPN output.

I am looking for the opposite, a way to turn RPN into highschool-math-class style infix notation, in order to represent RPN expressions from a database to lay users in an understandable way.

Please save your time and don't cook up the algorithm yourselves, just point me to textbook examples that I can't seem to find. Working backwards from the Shunting Yard algorithm and using my knowledge about the notations I'll probably be able to work up a solution. I'm just looking for a quick shortcut, so I don't have to reinvent the wheel.

Oh, and please don't tag this as "homework", I swear I'm out of school already! ;-)

Answer 1

google search, 3 results

Answer 2

Since RPN is also known as postfix notation, I tried googling convert "postfix to infix" and got quite a few results. The first several have code examples, but I found the RubyQuiz entry particularly enlightening.

Answer 3

If you're not worried about removing redundant parentheses, then the following Lisp code will work:

(defun rpn-to-inf (pre)
  (if (atom pre)
      pre
      (cond ((eq (car (last pre)) 'setf)
         (list (rpn-to-inf (first pre)) '= (rpn-to-inf (second pre))))
        ((eq (car (last pre)) 'expt)
         (list (rpn-to-inf (first pre)) '^ (rpn-to-inf (second pre))))
        (t (list (rpn-to-inf (first pre)) 
          (car (last pre)) 
          (rpn-to-inf (second pre)))))))