如何建立和/或树? [英] How to build an and-or tree?
问题描述
ab | c(d | e)
我想把它变成树。 因此,起初我们有两个或分支,可以下降
ab
或 c(d | e)
。如果您朝下 ab
分支,您将得到两个节点, a
和 b
(或 a
,后跟 b
,无论如何)。然后,如果您沿着 c(d | e)
分支,您将获得 c
和 (d | e)
,然后(d | e)
被拆分为 d
或 e
。 使树结构很简单你只需要一些类似
class Node {
string element;
Node [] children;
}
但是,你怎么知道孩子是否应该和 ?我猜每个级别的树应该在和和oring之间交替
有意义吗?任何人都可以为此建议一个结构?
有几个人建议在节点上存储运算符,即好的,但是没有办法利用每个级别总是交替的事实,或者,或者,和...?
编辑:不太确定为什么人们认为这是二叉树。 不是。我希望这个微小的代码段可以让你失望。
目前倾向于:
抽象类Node {}
class DataNode:Node
{
string data ;
}
抽象类OpNode:Node
{
Node [] children;
}
class OrNode:OpNode {}
class AndNode:OpNode {}
想想一个树结构,其中每个节点都表示一个布尔表达式,可以被评估为true或false - 在您的情况下,正则表达式(匹配或不匹配)。
树结构本身表示AND和OR:
每个路由,从根节点开始,以不再有子节点的结点结束,表示为AND的表达式。
树
A
/
B
/
C
将代表A AND B AND C。
每当一个节点有多个子节点时,有一个OR(分离),分支到几个路由:
A
/ \
BD
/
C
表示A AND((B AND C)或D)
所以你甚至不需要在任何地方存储运营商。
在您的示例中,您的表达式为 ab | c(d | e)
,因此没有常见的根表达式进行评估;我建议在这种情况下,根本就是简单的 true
,树将如下所示:
true
/ \
AC
/ / \
BDE
对于c#中的自定义树类,请查看树数据C#中的结构,或搜索或制作自己的一个。
I need a tree structure that supports "and" and "or"ing. For example, given a regular expression like ab|c(d|e)
I want to turn that into a tree.
So, at first we have two "or" branches... it can either go down ab
, or c(d|e)
. If you head down the ab
branch, you get two nodes, a
and b
(or a
followed by b
, whatever). Then if you go down the c(d|e)
branch, you get c
and (d|e)
, then (d|e)
is split into d
or e
.
Making a tree structure is easy, you just have something like
class Node {
string element;
Node[] children;
}
But then how do you know if the children should be "anded" or "ored"? I guess each level of the tree should alternate between "anding" and "oring"
Does that make sense? Can anyone suggest a structure for this?
A few people have suggested storing the "operator" on the node, which is fine, but isn't there a way to take advantage of the fact that each level always alternates or,and,or,and,...?
Edit: Not quite sure why people keep assuming this is a binary tree. It's not. I was hoping the tiny code snippet would tip you off. The example just happens to have only 2 branches.
Currently leaning towards this:
abstract class Node { }
class DataNode : Node
{
string data;
}
abstract class OpNode : Node
{
Node[] children;
}
class OrNode : OpNode { }
class AndNode : OpNode { }
Think of a tree structure where every node represents a boolean expression that can be evaluated to be either true or false - in your case a regular expression (match or non-match). The tree structure itself represents AND and OR: Each route, starting at the root node and ending with a node that has no further children, is a conjunction of expressions, representing AND. The tree
A
/
B
/
C
would represent A AND B AND C.
Whenever a node has more than 1 child node, there is an OR (disjunction), branching into several routes:
A
/ \
B D
/
C
represents A AND ((B AND C) OR D)
So you do not even need to store the operators anywhere.
In your example you have the expression ab|c(d|e)
so there is no common root expression to evaluate; I suggest the root in this case is simply true
and the tree would look like:
true
/ \
A C
/ / \
B D E
For a custom tree class in c# look here Tree data structure in C# or search on or make one of your own.
这篇关于如何建立和/或树?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!