Quelle est l'inversion de l'algorithme Shunting Yard?

Question

L'algorithme de triage Shunt Yard est utilisé pour analyser un notation infixe et génération de RPN .

Je cherche le contraire, un moyen de transformer RPN en notation infixe de style highschool-math-class, afin de représenter les expressions RPN d'une base de données afin de présenter les utilisateurs de manière compréhensible.

Économisez votre temps, ne créez pas vous-même l’algorithme, mais indiquez-moi des exemples de manuels scolaires que je n'arrive pas à trouver. En travaillant à partir de l'algorithme Shunting Yard et en utilisant mes connaissances sur les notations, je pourrai probablement trouver une solution. Je cherche simplement un raccourci rapide pour ne pas réinventer la roue.

Oh, et s'il vous plait, ne marquez pas ceci comme "devoirs", je jure que je sois déjà sorti de l'école! ; -)

Answer 1

Etant donné que RPN est également connu sous le nom de notation postfixe, j’ai essayé de chercher sur Google convertit "postfixe en infixe" et a obtenu quelques résultats. Plusieurs premiers ont des exemples de code, mais j'ai trouvé l'entrée RubyQuiz particulièrement enrichissante.

Answer 2

Si vous n'avez pas peur de supprimer les parenthèses redondantes, le code Lisp suivant fonctionnera:

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