如何建立一个和 - 或树？

Question

我需要一个支持"和"和"或"的树结构.例如,给定一个正则表达式,比如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;
}

但那么你怎么知道这些孩子应该"被"或""？我想树的每个级别应该在"anding"和"oring"之间交替

那有意义吗？谁能为此建议一个结构？

---

有些人建议在节点上存储"操作员",这很好,但是没有办法利用每个级别总是交替的事实,或者,和,和......？

编辑:不太确定人们为什么一直认为这是一棵二叉树.事实并非如此.我希望这个小小的代码片段会让你失望.这个例子碰巧只有2个分支.

---

目前倾向于此:

abstract class Node { }

class DataNode : Node
{
    string data;
}

abstract class OpNode : Node
{
    Node[] children;
}

class OrNode : OpNode { }
class AndNode : OpNode { }

Answer 1

想象一下树结构,其中每个节点表示一个布尔表达式,可以将其评估为true或false - 在您的情况下是正则表达式(匹配或不匹配).树结构本身表示AND和OR:每个路由从根节点开始并以没有其他子节点的节点结束,是表达式的组合,表示AND.那个树

    A
   /
  B
 /
C

代表A和B和C.

每当一个节点有超过1个子节点时,就会有一个OR(分离),分支到几个路由:

    A
   / \
  B   D
 /
C

代表A AND((B和C)或D)

所以你甚至不需要将操作员存储在任何地方.

在您的示例中,您有表达式,ab|c(d|e)因此没有要评估的公共根表达式; 我建议在这种情况下根是简单的true,树看起来像:

   true
   / \
  A   C
 /   / \
B   D   E

对于c#中的自定义树类,请在此处查看C#中的树数据结构,或者搜索或创建自己的树数据结构.

Answer 2

abstract class Node { }

class DataNode : Node {
    public string Data { get; }

    // details
}

class OperatorNode : Node {
    public Node Left { get; }
    public Node Right { get; }
    public BinaryOperator Operator { get; }

    // details
}

abstract class BinaryOperator { // details }

class Or : BinaryOperator { // details }
class And : BinaryOperator { // details }

Answer 3

您可以有两种类型的节点:运营商节点和变量节点.

树的叶子都是变量节点; 所有其他节点都是运营商节点.

二元运算符节点将有两个子节点.一元运算符(如NOT)节点将有1个子节点.

对于你的例子ab | c(d | e):

      OR
  /         \
 AND       AND
 / \      /  \
a   b    c   OR
           /  \
          d    e