0

这是伪作业（这是额外的功劳）。我有一个 BST，它是指向包含这些单词的行（存储在其他地方）的单词索引。我需要实现一种使用 s 表达式进行搜索的方法，以便可以组合和 (&) 和或 (|)。

在命令提示符下，用户可以键入如下内容：

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

本质上，这应该返回包含火、森林和水的所有行以及包含海洋、船和水的所有行。

我真正需要帮助的是解析节点并将其插入树中以正确表示表达式而不是实际代码的逻辑。我发现的唯一对我有意义的事情是为表达式中的每个单词返回一组行。然后根据它是“或”还是“与”操作，我将对这些集合执行联合或交集类型操作以创建一个新集合并将其传递到树上。

我对如何解析包含表达式的行有点迷茫。经过一番思考，似乎其中一个子表达式“越远”在我的 s 表达式树中应该越高？我想如果我能在正确的方向上推动解析和插入树中的表达式，我应该没问题。

我为上面的查询提出的示例树看起来像；

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

这是有道理的，因为 fire 将返回一组全部包含 fire 的行，而 forest 将返回一组全部包含 forest 的行。然后在“&”级别，我将采用这两个集合并创建另一个集合，其中仅包含两个集合中的线条，从而给我一个集合，其中只有包含火和森林的线条。

我的另一个绊脚石是在我克服了解析的障碍之后如何表示树中的所有内容。我有一个 ExpTreeNode 类，它将作为我的 ExpTree（BST）的节点，然后我有 2 个子类，运算符和操作数，但我不确定这是否是一个好方法。

4

1 回答 1

4

Dijkstra 已经为您完成了 :-)

尝试调车场算法：http ://en.wikipedia.org/wiki/Shunting-yard_algorithm

您可以使用调车场算法创建 RPN（反向波兰表示法），一旦创建，您可以通过它来创建二叉树。

通常，RPN 用于进行评估，但您实际上可以创建一棵树。

例如，您无需评估，而是创建树节点并将它们推入堆栈。

因此，如果您看到 node1, node2 , 运算符。您创建一个新节点

   Operator
   /     \
  node1   node2

并将其推回堆栈。

一个更详细的例子：

说表达式是(apples AND oranges) OR kiwis

对此的 RPN 是kiwis oranges apples AND OR

现在在保持堆栈的同时进行此操作。

将奇异果中的一个节点推入堆栈。橙子中的节点推入堆栈。苹果也一样。

所以堆栈是

Node:Apples
Node:Oranges
Node:Kiwis

现在您可以在 RPN 中看到 AND。

您从堆栈中弹出前两个并创建一个以 AND 作为父节点的新节点。

节点：AND，[节点：苹果，节点：橙子]

基本上是树

       AND
     /    \
  Apples  Oranges

现在将此节点推入堆栈。

所以堆栈是

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

现在您在 RPN 中看到 OR 并创建一个节点，其中 OR 作为父节点，Node:ANd 和 Node Kiwis 作为子节点获取树

           OR 
         /   \
       AND   Kiwis
     /    \
  Apples  Oranges

您甚至可以修改调车场算法来创建树，但处理 RPN 似乎更容易。

或者，您可以尝试使用递归下降解析技术。你问的很常见，即使你在网上搜索也能找到语法和代码。

顺便说一句，你的意思是二叉树对吧？BST（二叉搜索树）有一个额外的约束......

于 2011-04-13T17:14:48.123 回答