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! ;-)
Solution
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.
OTHER TIPS
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)))))))