c# - 如何构建一棵与或树？

Question

我需要一个支持“与”和“或”的树结构。例如，给定一个像 ab|c(d|e) 这样的正则表达式，我想把它变成一棵树。

所以，一开始我们有两个“或”分支……它可以沿着 ab 或 c(d|e) 向下。如果你往下 ab 分支，你会得到两个节点，a 和 b(或 a 后跟 b，随便什么)。然后如果你沿着 c(d|e) 分支，你会得到 c and (d|e)，则(d|e)被拆分为d或e。

制作树状结构很简单，你只要有类似的东西

class Node {
    string element;
    Node[] children;
}

但是你怎么知道 child 应该被“anded”还是“ored”呢？我想树的每一层都应该在“anding”和“oring”之间交替

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

---

一些人建议在节点上存储“运算符”，这很好，但是没有办法利用每个级别总是交替 or,and,or,and... ？

编辑:不太清楚为什么人们总是假设这是一个二叉树。 不是。我希望这个微小的代码片段能给你提示。该示例恰好只有 2 个分支。

---

目前倾向于这个:

abstract class Node { }

class DataNode : Node
{
    string data;
}

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

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

Answer 1

考虑一个树结构，其中每个节点代表一个 bool 表达式，可以评估为真或假 - 在您的情况下是正则表达式(匹配或不匹配)。树结构本身代表AND和OR:每条路线，从根节点开始，以没有更多子节点的节点结束，是表达式的结合，表示 AND。树

    A
   /
  B
 /
C

将代表 A AND B AND C。

每当一个节点有超过 1 个子节点时，就会有一个 OR(分离)，分支成几条路线:

    A
   / \
  B   D
 /
C

代表A AND ((B AND C) OR D)

因此您甚至不需要在任何地方存储运算符。

在您的示例中，您有表达式 ab|c(d|e) 因此没有要计算的公共(public)根表达式；我建议在这种情况下的根只是 true 并且树看起来像:

   true
   / \
  A   C
 /   / \
B   D   E

对于 c# 中的自定义树类，请看这里 Tree data structure in C#或搜索或自己制作一个。