¿Cuál es la inversión del algoritmo de Shunting Yard?

Question

El Shunting Yard algorithm de Dijkstra se usa para analizar una notación infija y generar RPN de salida.

Estoy buscando lo contrario, una forma de convertir RPN en una notación infija estilo highschool-math-class, para representar las expresiones RPN de una base de datos para que los usuarios laigan de una manera comprensible.

Por favor, ahorre su tiempo y no cocine el algoritmo por sí mismo, solo bríndeme ejemplos de libros de texto que parece que no puedo encontrar. Trabajando hacia atrás desde el algoritmo de Shunting Yard y usando mi conocimiento sobre las notaciones, probablemente pueda encontrar una solución. Solo estoy buscando un atajo rápido, así que no tengo que reinventar la rueda.

Ah, y por favor no etiquetar esto como "tarea", I juro ¡Ya no estoy! ;-)

Answer 1

Como RPN también se conoce como notación de postfijo, traté de buscar en Google convert "postfix to infix" y obtuve algunos resultados. Los primeros varios tienen ejemplos de código, pero encontré el RubyQuiz entry particularmente esclarecedor.

Answer 2

Si no está preocupado por la eliminación de paréntesis redundantes, entonces el siguiente código Lisp funcionará:

(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)))))))