Shunting Yardアルゴリズムの逆転は何ですか？

Question

DijkstraのShunting Yard algorithmは、インフィックス表記を解析し、RPN出力を生成するために使用されます。

RPNをデータベースから理解しやすい方法で表現するために、RPNを高等学校の数学クラスのスタイルインキ表記に変える方法を探しています。

あなたの時間を節約し、自分自身でアルゴリズムを調理しないでください。見つけられないような教科書の例を教えてください。 Shunting Yardアルゴリズムから後ろ向きに作業し、私の知識を使って私はおそらく解決策を打ち立てることができます。私はちょうど簡単なショートカットを探しているので、私は車輪を再発明する必要はありません。

ああ、これを「宿題」とタグ付けしないでください。私はを誓います私はすでに学校に通っていません！ ;-)

Answer 1

RPNは後置記号としても知られているので、私はグーグルconvert "postfix to infix"を試して、かなりの結果を得ました。最初のいくつかにコード例がありますが、私はRubyQuiz entryが特に啓発されていることがわかりました。

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