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

Question

Dijkstra's Algoritmo del patio de maniobras se utiliza para analizar una notación infija y generar RPN producción.

Estoy buscando lo contrario, una forma de convertir RPN en notación infija al estilo de una clase de matemáticas de secundaria, para representar expresiones RPN de una base de datos para usuarios no profesionales de una manera comprensible.

Ahorre tiempo y no invente el algoritmo usted mismo, solo indíqueme ejemplos de libros de texto que parece que no puedo encontrar.Trabajando hacia atrás desde el algoritmo Shunting Yard y utilizando mi conocimiento sobre las notaciones, probablemente podré encontrar una solución.Solo estoy buscando un atajo rápido, para no tener que reinventar la rueda.

Ah, y por favor no etiquetes esto como "tarea". jurar ¡Ya salí de la escuela!;-)

Answer 1

Como RPN también se conoce como notación postfija, intenté buscar en Google convertir "postfijo a infijo" y obtuve bastantes resultados.Los primeros tienen ejemplos de código, pero encontré el Entrada de RubyQuiz particularmente esclarecedor.

Answer 2

Si no le preocupa eliminar paréntesis redundantes, 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)))))))