0

これは疑似宿題です（追加のクレジットです）。単語を含む（別の場所に格納されている）行を指す単語のインデックスであるBSTがあります。and（＆）and or（|）を組み合わせることができるように、S式を使用して検索する方法を実装する必要があります。

コマンドプロンプトで、ユーザーは次のように入力できます。

QUERY ((((fire)&(forest))|((ocean)&(boat)))&(water))

基本的に、これは、fire、forest、waterという単語を含むすべての行と、海、ボート、および水を含むすべての行を返す必要があります。

私が本当に助けを必要としているのは、実際のコードよりも式を適切に表現するために、ノードを解析してツリーに挿入するためのロジックです。私が理解できる唯一のことは、式の各単語の一連の行を返すことです。次に、それが「or」または「and」操作であるかどうかに応じて、それらのセットに対して和集合または交差型の操作を実行して、新しいセットを作成し、それをツリーに渡します。

式を含む行を解析する方法に少し迷っています。いくつか考えた後、サブ式の1つから「遠い」方が、私のs式ツリーでより高いはずであるように見えますか？式を解析してツリーに挿入する限り、正しい方向にプッシュできれば大丈夫だと思います。

上記のクエリ用に思いついたサンプルツリーは、次のようになります。

                                            &
                                         /     \
                                       |       water
                                   /      \
                                 &          &
                               /   \        /   \
                            fire  forest  ocean boat

これは、火がすべて火を含む行のセットを返し、森がすべて森を含む行のセットを返すため、理にかなっています。次に、「＆」レベルで、これら2つのセットを取得し、両方のセットに含まれる行のみを含む別のセットを作成します。これにより、火と森の両方を含む行のみを含むセットが得られます。

私の他のつまずきは、構文解析のハードルを克服した後、ツリー内のすべてを表現する方法です。ExpTree（BST）のノードとして機能するExpTreeNodeクラスがあり、次に演算子とオペランドの2つのサブクラスがありますが、これが適切なアプローチかどうかはわかりません。

4

1 に答える 1

4

ダイクストラはすでにあなたのためにそれをしました:-)

操車場アルゴリズムを試してください：http：//en.wikipedia.org/wiki/Shunting-yard_algorithm

操車場アルゴリズムを使用してRPN（逆ポーランド記法）を作成できます。RPNが作成されたら、それをパスしてバイナリツリーを作成できます。

通常、RPNを使用して評価を行いますが、実際にツリーを作成することもできます。

たとえば、評価する代わりに、ツリーノードを作成してスタックにプッシュします。

したがって、node1、node2、operatorが表示されている場合。新しいノードを作成します

   Operator
   /     \
  node1   node2

スタックに押し戻します。

より詳細な例：

式が(apples AND oranges) OR kiwis

このためのRPNはkiwis oranges apples AND OR

スタックを維持しながらこれを歩きます。

キウイからノードをスタックにプッシュします。オレンジのノードがスタックにプッシュされます。リンゴも同じです。

つまり、スタックは

Node:Apples
Node:Oranges
Node:Kiwis

これで、RPNにANDが表示されます。

スタックから上位2つをポップし、ANDを親として新しいノードを作成します。

ノード：AND、[ノード：リンゴ、ノード：オレンジ]

基本的に木

       AND
     /    \
  Apples  Oranges

次に、このノードをスタックにプッシュします。

つまり、スタックは

Node:AND, [Node:Apples, Node:Oranges]
Node:Kiwis

これで、RPNにORが表示され、ORを親として、Node：ANdとNodeKiwisを子としてツリーを取得するノードを作成します。

           OR 
         /   \
       AND   Kiwis
     /    \
  Apples  Oranges

操車場アルゴリズムを変更してツリーを作成することもできますが、RPNの処理は簡単なようです。

または、再帰下降解析手法を使用してみることができます。あなたが尋ねることは非常に一般的であり、あなたがウェブを検索したとしても、あなたは文法とコードを見つけることができるでしょう。

ちなみに、二分木という意味ですか？BST（二分探索木）には追加の制約があります...

于 2011-04-13T17:14:48.123 に答える