操車場アルゴリズムの反転とは何ですか?

Question

ディクストラの 操車場のアルゴリズム 中置記法を解析して生成するために使用されます。 RPN 出力。

私はその逆、RPN を高校の数学の授業スタイルの中置記法に変換して、データベースからの RPN 式を一般ユーザーにわかりやすい方法で表現する方法を探しています。

時間を節約してください。アルゴリズムを自分で組み立てずに、私が見つけられそうにない教科書の例を教えてください。操車場アルゴリズムから逆算して、表記法に関する知識を利用すれば、おそらく解決策を導き出せるでしょう。車輪を再発明する必要がないように、簡単なショートカットを探しているだけです。

ああ、これに「宿題」というタグを付けないでください。 誓う もう学校を卒業しました！;-)

Answer 1

RPNは後置記法とも呼ばれるのでググってみました 「後置を中置に」変換します そしてかなりの結果が得られました。最初のいくつかにはコード例が含まれていますが、 Rubyクイズのエントリー 特に啓発的です。

Answer 2

冗長な括弧の削除を気にしない場合は、次の 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)))))))