Qual è l'inversione dell'algoritmo Shunt Yard?

Question

Quello di Dijkstra Algoritmo dello scalo di manovra viene utilizzato per analizzare una notazione infissa e generare RPN produzione.

Sto cercando il contrario, un modo per trasformare RPN in una notazione infissa in stile scuola di matematica, al fine di rappresentare le espressioni RPN da un database per gli utenti in modo comprensibile.

Per favore, risparmia tempo e non inventare l'algoritmo da solo, indicami solo esempi di libri di testo che non riesco a trovare.Lavorando a ritroso dall'algoritmo Shunting Yard e utilizzando la mia conoscenza delle notazioni, probabilmente sarò in grado di trovare una soluzione.Sto solo cercando una scorciatoia veloce, così non devo reinventare la ruota.

Oh, e per favore non etichettarli come "compiti a casa", I imprecare Ho già finito la scuola!;-)

Answer 1

Poiché RPN è noto anche come notazione postfissa, ho provato a cercare su Google convertire "postfisso in infisso" e ho ottenuto parecchi risultati.I primi hanno esempi di codice, ma ho trovato il file Voce RubyQuiz particolarmente illuminante.

Answer 2

Se non sei preoccupato di rimuovere le parentesi ridondanti, funzionerà il seguente codice Lisp:

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