How to build a and-or tree?

Question

I need a tree structure that supports both and and ing. For example, with a regular expression like ab|c(d|e) I want to turn this into a tree.

So, first we have two "or" branches ... it can either go down ab or c(d|e) . If you head the ab branch, you get two nodes: a and b (or a , and then b , whatever). Then, if you omit the branch c(d|e) , you get c and (d|e) , then (d|e) splits into d or e .

Creating a tree structure is easy, you just have something like

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

But how do you know whether children should "be" or "scold"? I think each level of the tree should alternate between "anding" and "oring"

It makes sense? Can anyone suggest a framework for this?

---

Several people suggested saving the “statement” to node, which is good, but there is no way to take advantage of the fact that each level always alternates either, and, or, and ...

Edit: It's not entirely clear why people think this is a binary tree. Not this. I was hoping a tiny piece of code would tell you. The example just has only 2 branches.

---

Currently leaning toward this:

 abstract class Node { } class DataNode : Node { string data; } abstract class OpNode : Node { Node[] children; } class OrNode : OpNode { } class AndNode : OpNode { } 

Answer 1

Think of a tree structure where each node is a logical expression that can be evaluated as true or false, in your case a regular expression (match or mismatch). The tree structure itself is AND and OR: Each route starting at the root of a node and ending at node that has no other children is a conjunction of expressions representing AND. Wood

  A / B / C 

will represent A AND B AND C.

Whenever a node has more than one child node, there is an OR (disjunction) branching into several routes:

  A / \ BD / C 

represents A AND ((B AND C) OR D)

This way, you don’t even need to store statements anywhere.

In your example, you have the expression ab|c(d|e) , so there is no common root expression for the calculation; I suggest that the root in this case is just true , and the tree will look like this:

  true / \ AC / / \ BDE 

For a custom tree class in C #, see here The data structure of the tree in C # or search or make one of your own.

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

You can have 2 types of nodes: operator nodes and variable nodes.

The leaves of your tree will all be variable nodes; all other nodes will be operator nodes.

Binary operator nodes will have two children. A unary operator (for example, NOT) must have 1 child.

For your example ab | c (d | e):

  OR / \ AND AND / \ / \ abc OR / \ de 

Answer 4

Something is wrong with this:

 enum Operation { None, And, Or } class Node { string element; Node[] children; Operation operation; } 

Edit:

As an example of how ab|c(d|e) would look something like this:

 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"} } } } } } }; 

Answer 5

I did this just a few days ago using ANTLR . ANTLR provided me with a grammar that is presented as an abstract AST syntax tree, as you just described, and it generated C # code that could handle this grammar.

It is pretty cute and elegant. The following are a few examples .

Answer 6

Just to add a little different

 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<T> : Node { T _data; public DataNode(T data) { _data = data; } public override string ToString() { return _data.ToString(); } } 

Answer 7

How about something so simple:

 class OrNode { string element; AndNode[] children; } class AndNode { string element; OrNode[] children; } 

Each class can have its own evaluate() , which should be AND or OR for all children as needed.

You can still have a parent superclass so that your code can contain shared nodes without worrying about whether the first one was AND OR OR.