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

notación posfija

Question

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

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

Por favor, ahorren su tiempo y no cocinen el algoritmo ustedes mismos, solo apúntenme a 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 etiquetes esto como "tarea", ¡te juro que ya estoy fuera de la escuela! ;-)

Answer 1

Como RPN también se conoce como notación de postfijo, traté de convertir google "postfix a infijo" y obtuve bastantes resultados. Los primeros varios tienen ejemplos de código, pero encontré la entrada RubyQuiz particularmente esclarecedora.

Answer 2

Si no te preocupa eliminar los 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)))))))