Was ist die Inversion des Shunting Yard Algorithmus?

Question

Dijkstra Shunting Yard algorithm wird verwendet, um eine Infix-Notation zu analysieren und RPN Ausgabe zu generieren.

Ich bin auf der Suche nach dem Gegenteil, eine Möglichkeit, RPN in Highschool-Math-Klasse Stil Infix Notation zu verwandeln, um RPN Ausdrücke aus einer Datenbank darzustellen, um Benutzer in verständlicher Weise zu legen.

Bitte speichern Sie Ihre Zeit und kochen Sie nicht den Algorithmus selbst, zeigen Sie mich einfach auf Lehrbuch Beispiele, die ich nicht finden kann. Indem ich rückwärts vom Shunting Yard-Algorithmus arbeite und mein Wissen über die Notationen nutze, werde ich wahrscheinlich in der Lage sein, eine Lösung zu finden. Ich suche nur eine schnelle Abkürzung, damit ich das Rad nicht neu erfinden muss.

Oh, und bitte nicht dies als "Hausaufgaben", I Fluch Ich bin schon aus der Schule! ;-)

Answer 1

Da RPN auch als Postfix-Notation bekannt ist, habe ich versucht, googlen convert "postfix to infix" und habe ziemlich viele Ergebnisse. Die ersten haben einige Codebeispiele, aber ich fand die RubyQuiz entry besonders aufschlussreich.

Answer 2

Wenn Sie über das Entfernen von redundanten Klammern nicht besorgt sind, dann wird der folgende Lisp-Code funktioniert:

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