c# - 数式から二分木を作成

Question

みたいな表情をしています((2+8)*8)-(5*(5+2)) Or + 2 + 1 1。そしてその中に二分木を作りたい。

  +
 / \
2   +
   / \
  1   1

このバイナリツリーを作成するにはどうすればよいですか?

Answer 1

私は同様のプロジェクトを持っていましたが、これが私がやった方法です:

1. 文字列をトークン化します。各シンボルが何であるかを参照してください。たとえば、リストには次のものが含まれる場合があります。

   '(' 左括弧
   '11' 番号
   「+」演算子など

2. 式を後置 (または必要に応じて前置) 表記に変換します。これを行うことができる 1 つのアルゴリズムは、Shunting Yard アルゴリズムと呼ばれます。後置表記法の利点は、スタックベースの方法 (または必要に応じてバイナリ ツリー) を使用して、式をより簡単に評価できることです。

3. 後置式を評価します。二分木とスタックの 2 つの方法でそれを行うことができます。

スタック評価:

後置表記に変換された式の例は、次のようになります。

2 8 + 8 * 5 5 2 + * -

評価は次のように行われます: 数値に遭遇したら、それをスタックにプッシュします。演算子に遭遇したら、スタックから 2 つのアイテムをポップし、計算を行い、結果をスタックにプッシュします。最終的には、最終結果を残す必要があります。

上記の例では、次のようにします。

Push 2 [Stack content: 2]
Push 8 [2 8]
Pop 2 and 8 []
Push 2+8 [10]
Push 8 [10 8]
Pop 10 and 8 []
Push 10*8 [80]
Push 5 [80 5]
Push 5 [80 5 5]
Push 2 [80 5 5 2]
Pop 2 and 5 [80 5]
Push 2 + 5 [80 5 7]
Pop 7 and 5 [80]
Push 7 * 5 [80 35]
Pop 80 and 35 []
Push 80 - 35 [45]
Final result is 45.

二分木

これが私が行う方法です。スタックベースのアプローチと同様に、ノードのスタックを使用します。演算子に遭遇すると、スタックから 2 つのアイテムをポップしますが、評価する代わりに、演算子でノードを作成し、ポップされた 2 つのアイテムの親にします。次に、ノードをスタックにプッシュします。

このアプローチの欠点は、ツリーの作成という追加のステップがあることです。

最終的な注意事項

これは私が使用する方法です。これよりも効率的な方法があるかもしれませんが、これが私のやり方です。

Answer 2

以下は、中置文字列から二分式ツリーを作成するための C++ コードです。