¿Cómo construir un árbol y?

Question

Necesito una estructura de árbol que admita "y" y "o" ing. Por ejemplo, dada una expresión regular como ab|c(d|e) quiero convertir eso en un árbol.

Entonces, al principio tenemos dos "o" ramas ... puede ir hacia abajo ab, o c(d|e). Si va por la rama ab, obtiene dos nodos, ayb (o a seguido de b, lo que sea). Entonces, si hay que bajar la rama c(d|e), se obtiene c y (d|e), entonces (d|e) se divide en doe.

La fabricación de una estructura de árbol es fácil, sólo tiene algo así como

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

Pero entonces, ¿cómo saber si los niños deben estar "unidos mediante AND" o "ORED"? Creo que cada nivel del árbol debe alternar entre "AND" y "junta tórica" ​​

¿Eso tiene sentido? ¿Alguien puede sugerir una estructura para esto?

---

Algunas personas han sugerido que almacena el "operador" en el nodo, lo cual está bien, pero no hay una manera de aprovechar el hecho de que cada nivel se alterna siempre o, AND, OR, y , ...?

Edit: No estoy seguro de por qué la gente sigue asumiendo que este es un árbol binario. No es. Esperaba que el pequeño fragmento de código te avisara. El ejemplo solo ocurre para tener solo 2 ramas.

---

Actualmente inclinando hacia esto:

abstract class Node { } 

class DataNode : Node 
{ 
    string data; 
} 

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

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

Answer 1

Piense en una estructura de árbol donde cada nodo representa una expresión booleana que puede evaluarse como verdadera o falsa, en su caso una expresión regular (coincidencia o no coincidencia). La estructura de árbol en sí representa AND y OR: Cada ruta, comenzando en el nodo raíz y terminando con un nodo que no tiene más hijos, es una conjunción de expresiones que representa AND. El árbol

A 
/
    B 
/
C 

representarían un Y B y C.

Siempre que un nodo tiene más del 1 nodo hijo, hay un OR (disyunción), la ramificación en varias rutas:

A 
/\ 
    B D 
/
C 

representa A AND ((B y C) O D)

Así que ni siquiera necesita almacenar los operadores en ningún lado.

En su ejemplo tiene la expresión ab|c(d|e) por lo que no hay una expresión de raíz común para evaluar; Sugiero la raíz en este caso es simplemente true y el árbol se vería así:

true 
/\ 
    A C 
//\ 
B D E 

Para una clase de árbol personalizado en C# mira aquí Tree data structure in C# o buscar o hacer uno propio.

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

¿Hay algo de malo en esto:

enum Operation 
{ 
    None, 
    And, 
    Or 
} 

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

Editar:

Como un ejemplo de cómo ab|c(d|e) se vería algo como esto:

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 4

Lo hice hace unos días usando ANTLR. ANTLR me proporcionó una gramática que se representa como un árbol de sintaxis abstracta de AST tal como lo acaba de describir y generó el código C# que podría manejar esa gramática.

Es bastante agradable y elegante. Aquí hay un few example.

Answer 5

Puede tener 2 tipos de nodos: nodos de operador y nodos variables.

Las hojas de su árbol serían todos nodos variables; todos los demás nodos serían nodos de operador.

Los nodos del operador binario tendrían dos hijos. Los nodos del operador unario (como NOT) tendrían 1 hijo.

Para su ejemplo ab | c (d | e):

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

Answer 6

solo para arrojarlo en un poco diferente uno

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

¿Qué tal algo así de simple:

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

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

Cada clase podría tener su propio evaluate() que AND y O todos los niños según sea necesario

Es posible que desee tener una superclase primaria para que su código pueda contener nodos genéricos sin preocuparse de si el primero fue AND u OR.