采用集和二叉搜索树解析和建筑S-防爆pressions [英] Parsing and building S-Expressions using Sets and binary search tree

问题描述

这是伪作业（这是额外的学分）。我有一个BST它是一个指向包含字线（存储在别处）字样的索引。我需要实现的方式使用S-EX pressions这样我就可以结合搜索和（安培）。和或（|）

This is pseudo homework (it's extra credit). I've got a BST which is an index of words that point to the lines (stored somewhere else) that contain the words. I need to implement a way to search using s-expressions so I can combine and (&) and or (|).

在命令提示符下用户可以键入类似：

At the command prompt a user could type something like:

查询（（（（火）及（林））|（（海洋）及（船）））及（水））

从本质上讲，应该返回包含单词消防，森林和水，以及包含海洋，舟和水的所有行的所有行。

Essentially that should return all lines that contain the words fire, forest and water as well as all lines that contain ocean, boat and water.

我真正需要帮助的逻辑分析和节点插入到树正确地重新present前pression比实际code以上。我曾指出，唯一对我来说很有意义返回一个套系在EX pression每一个字。然后，根据它是否是一个或或和操作我会在这些集执行一个集或交集式操作来创建新组和传递上了树。

What I really need help with is the logic for parsing and inserting nodes into the tree to properly represent the expression more than the actual code. The only thing I have worked out that makes sense to me is returning a set of lines for each word in the expression. Then depending on if it's an "or" or "and" operation I would perform a union or intersection type operation on those sets to create a new set and pass that on up the tree.

我迷失在如何解析包含EX pression行。经过一番思想看来，远了子前pressions之一是较高的，应该是我的S-EX pression树？我想，如果我能得到一推在正确的方向，只要分析和树插入前pressions我应该没问题。

I am kind of lost on how to parse the line that contains the expression. After some thought it appears that the "farther" out one of the sub-expressions is the higher it should be in my s-expression tree? I think if I could just get a push in the right direction as far as parsing and inserting the expressions in the tree I should be OK.

我的样本树;

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

这是有道理的火灾将返回一组都包含火灾和森林将返回一组都包含森林行的行。然后在与＆amp;水平我会采取这两组，并创建另一组包含只有那些在两套从而给了我一组只有同时包含火灾和森林线的线。

This makes sense as fire would return a set of lines that all contain fire and forest would return a set of lines that all contain forest. Then at the "&" level I would take those two sets and create another set that contained only the lines that were in both sets thus giving me a set that only has lines which contain both fire and forest.

我的另一个绊脚石是如何重新present一切都在树上我克服了解析的障碍后。我将作为我的ExpTree（在BST）节点的ExpTreeNode类，然后我有2个亚类，运算符和操作数，但我不知道这是一个不错的办法。

My other stumbling block is how to represent everything in the tree after I overcome the hurdle of parsing. I have an ExpTreeNode class that will serve as the nodes for my ExpTree(the BST) and then I have 2 subclasses, operator and operand, but I'm not sure if this is a good approach.

推荐答案

Dijkstra算法做它已经为你： - ）

Dijkstra has done it for you already :-)

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

您可以使用调车场算法创建RPN（逆波兰式），并且一旦被创建，你可以做一个通过它来创建二叉树。

You can create the RPN (reverse polish notation) using the shunting yard algorithm, and once that is created, you can make a pass through it to create the binary tree.

通常情况下，RPN是用来做评价，但实际上你可以创建一个树。

Normally, the RPN is used to do the evaluation, but you can actually create a tree.

有关实例，而不是评估，创建树节点，并把他们压入堆栈。

For instance, instead of evaluating, you create tree nodes and push them onto the stack.

所以，如果你看到节点1，节点2，运营商。您创建一个新节点

So if you see node1, node2 , operator. You create a new node

   Operator
   /     \
  node1   node2

和它推回入堆栈。

有一个更详细的例子：

说前pression是（苹果和橘子）或猕猴桃

Say the expression is (apples AND oranges) OR kiwis

在RPN因为这是猕猴桃桔子苹果，或

现在，同时保持一摞走这一点。

Now walk this while maintaining a stack.

请一个节点出猕猴桃推入堆栈。节点出橘子推入堆栈。同样的，苹果。

Make a node out of kiwis push onto stack. Node out of oranges push onto stack. Same with apples.

所以堆栈

Node:Apples
Node:Oranges
Node:Kiwis

现在你看到的和RPN。

Now you see the AND in the RPN.

您弹出前两名从堆栈中创建一个新的节点与父。

You pop the top two from the stack and create a new Node with AND as parent.

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

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

基本上树

       AND
     /    \
  Apples  Oranges

现在推这个节点入堆栈。

Now push this node onto stack.

所以堆栈

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

现在你看到或RPN，并创建一个节点或父和节点：与节点和新西兰人儿童得到树

Now you see the OR in the RPN and create a node with OR as parent and Node:ANd and Node Kiwis as children getting the tree

           OR 
         /   \
       AND   Kiwis
     /    \
  Apples  Oranges

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

You might even be able to modify the shunting yard algorithm to create the tree, but dealing with the RPN seems easier.

另外，您可以尝试使用递归下降解析技术。你问什么是很常见的，你将能够找到语法和code就算了，如果你在网上搜索。

Alternately, you can try using Recursive Descent Parsing techniques. What you ask is very common and you will be able to find grammars and code even, if you search the web.

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

By the way, you just mean Binary tree right? BST (Binary Search Tree) has an extra constraint...

这篇关于采用集和二叉搜索树解析和建筑S-防爆pressions的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！