algorithm - 使用集合和二叉搜索树解析和构建 S 表达式

Question

这是伪作业(它是额外的学分)。我有一个 BST，它是指向包含单词的行(存储在其他地方)的单词索引。我需要实现一种使用 s 表达式进行搜索的方法，以便我可以将 and (&) 和 or (|) 结合起来。

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

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

基本上，这应该返回所有包含 fire、forest 和 water 的行，以及所有包含 ocean、boat 和 water 的行。

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

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

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

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

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

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

Answer 1

Dijkstra 已经为您完成了:-)

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

您可以使用调车场算法创建 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。

您从堆栈中弹出顶部的两个节点并创建一个以 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(二叉搜索树)有一个额外的约束...