キューの再帰的計算

Question

キュー内にいくつかの要素があります（たとえば、/ - 4 2 + 4 5）。

(4-2)/(4+5)として計算する必要があります。誰かが私に説明することができます 再帰これについてのアルゴリズム？

Answer 1

ロジック、算術、代数の表記法の形式であるpolish notationを理解しようとします。

数字4と5を追加する式は、接頭辞/ポーランド表記では4 + 5ではなく+ 4 5と書かれています。

数字4と2を減算する式は、接頭辞/ポーランド表記で4 - 2ではなく- 4 2と書かれています。

次に、操作を構成できます。 op1、op2、op3は+、-、*、/ことができる(m1 op1 n1) op3 (m2 op2 n2)、と解釈することができるop3 (op1 m1 n1) (op2 m2 n2)、。

括弧は任意であり、前ポーランド記法は op3 op1 m1 n1 op2 m2 n2

それを理解するための最も簡単な方法を記述することができ、ツリーを使用することです。ツリーはまた、そのような表記を評価するために使用される再帰アルゴリズムをよりよく理解するのに役立ちます。このようなツリーでは、どの操作もノードとみなされ、数字は葉です。

は、式を評価するためには、必要があります：それは演算子と数字を識別するのに構成され、準ツリーを構築：

• は式を解析します。
• 作成したツリーにアクセスしてすべての操作を評価し、最終結果を生成します。