12

Dijkstra のShunting Yard アルゴリズムを使用して、中置表記を解析し、RPN出力を生成します。

私は反対に、RPN を高校の数学クラスのスタイルの中置記法に変換する方法を探しています。これは、データベースからの RPN 式を一般ユーザーにわかりやすい方法で表現するためです。

時間を節約して、自分でアルゴリズムを作成しないでください。見つけられないように見える教科書の例を教えてください。Shunting Yard アルゴリズムから逆算して、表記法に関する私の知識を使用すると、おそらく解決策を見つけることができるでしょう。簡単な近道を探しているだけなので、一からやり直す必要はありません。

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

4

2 に答える 2

7

RPNは後置記法としても知られているので、 「後置から中置」にグーグル変換してみたところ、かなりの数の結果が得られました。最初のいくつかにはコード例がありますが、RubyQuizエントリは特に啓発的であることがわかりました。

于 2008-09-17T19:52:50.457 に答える
6

冗長な括弧を削除する心配がない場合は、次の 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)))))))
于 2008-09-17T19:59:53.217 に答える