如何建立一个和 – 或树？
我需要一个支持“和”和“或”的树结构。 例如，给定像ab|c(d|e)这样的正则表达式，我想将其转换为树。
所以，起初我们有两个“或”分支……它可以向下走，也可以向下走c(d|e) 。 如果你沿着ab分支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 { }
想象一下树结构，其中每个节点都表示一个布尔表达式，可以将其计算为true或false – 在您的情况下是正则表达式（匹配或不匹配）。 树结构本身表示AND和OR：每个路由从根节点开始，以没有其他子节点的节点结束，是表达式的组合，表示AND。 那个树
A / B / C
代表A和B和C.
每当一个节点有超过1个子节点时，就会有一个OR（析取），分支到几个路由：
A / \ BD / C
代表A AND（（B和C）或D）
所以你甚至不需要将操作员存储在任何地方。
在您的示例中，您使用表达式ab|c(d|e)因此没有要评估的公共根表达式; 我建议在这种情况下根是true ，树看起来像：
true / \ AC / / \ BDE
对于c＃中的自定义树类，请在此处查看C＃中的树数据结构，或者搜索或创建自己的树数据结构 。
您可以有两种类型的节点：运营商节点和变量节点。
树的叶子都是变量节点; 所有其他节点都是运营商节点。
二元运算符节点将有两个子节点。 一元运算符（如NOT）节点将有1个子节点。
对于你的例子ab | c（d | e）：
OR / \ AND AND / \ / \ abc OR / \ de
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 }
这有什么不妥之处：
enum Operation { None, And, Or } class Node { string element; Node[] children; Operation operation; }
编辑：
作为ab|c(d|e)如何看起来像这样的例子：
Node root = new Node { operation = Operation.Or, children = new Node[] { new Node { operation = Operation.And, children = new Node[] { new Node{ element = "a" }, new Node{ element="b" } } }, new Node { children = new Node[] { new Node{ element = "c"}, new Node { operation= Operation.Or, children = new Node[] { new Node{ element= "d"}, new Node{element = "e"} } } } } } };
我几天前用ANTLR做过这个。 ANTLR为我提供了一个语法，它表示为刚刚描述的AST抽象语法树，它生成了可以处理该语法的c＃代码。
它非常漂亮和优雅。 这是一些例子 。
只是扔一个稍微不同的一个
interface Node { // top level operations here } class OpNode : Node { public Node Left { get; set; } public Node Right { get; set; } } class AndNode : OpNode { public AndNode(Node left, Node right) { Left = left; Right = right; } public override string ToString() { return "(" + Left.ToString() + " & " + Right.ToString() + ")"; } } class OrNode : OpNode { public OrNode(Node left, Node right) { Left = left; Right = right; } public override string ToString() { return "(" + Left.ToString() + " | " + Right.ToString() + ")"; } } class DataNode : Node { T _data; public DataNode(T data) { _data = data; } public override string ToString() { return _data.ToString(); } }
这个简单的事情怎么样：
class OrNode { string element; AndNode[] children; } class AndNode { string element; OrNode[] children; }
每个类都有自己的evaluate() ，它可以根据需要对所有子项进行AND或OR
您可能仍希望拥有父超类，以便您的代码可以保存通用节点，而无需担心第一个是AND还是OR。