Как построить и / или дерево?

Question

Мне нужна древовидная структура, которая поддерживает «и» и «или» ing. Например, учитывая регулярное выражение типа 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

Подумайте о древовидной структуре, где каждый узел представляет логическое выражение, которое можно оценить как истинное или ложное - в вашем случае регулярное выражение (совпадающее или не совпадающее). Сама древовидная структура представляет собой И и ИЛИ: Каждый маршрут, начинающийся с корневого узла и заканчивающийся узлом, у которого больше нет дочерних элементов, является соединением выражений, представляющих AND. Дерево

    A
   /
  B
 /
C

будет представлять А, В и С.

Всякий раз, когда узел имеет более 1 дочернего узла, возникает OR (дизъюнкция), разветвляющаяся на несколько маршрутов:

    A
   / \
  B   D
 /
C

представляет собой А И ((В И С) ИЛИ D)

Так что вам даже не нужно хранить операторов где-либо.

В вашем примере у вас есть выражение ab|c(d|e), поэтому нет общего корневого выражения для оценки; Я полагаю, что корень в этом случае просто true и дерево будет выглядеть так:

   true
   / \
  A   C
 /   / \
B   D   E

Пользовательский класс дерева в c # можно посмотреть здесь Структура данных дерева в C # или выполнить поиск или создать свой собственный.

Answer 2

Вы можете иметь 2 типа узлов: узлы операторов и узлы переменных.

Листья вашего дерева будут переменными узлами; все остальные узлы будут операторами.

Узлы бинарных операторов будут иметь двух детей. Узлы с унарным оператором (например, NOT) будут иметь 1 дочерний элемент.

Для вашего примера ab | c (d | e):

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

Answer 3

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 4

Что-то не так с этим:

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

Answer 5

Как насчет чего-то такого простого:

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

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

У каждого класса может быть свой evaluate(), который будет И или ИЛИ всем детям по мере необходимости

Возможно, вы все еще хотите иметь родительский суперкласс, чтобы ваш код мог содержать общие узлы, не беспокоясь о том, был ли первый AND или OR.

Answer 6

Просто добавить немного другой

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

Я сделал это всего несколько дней назад, используя ANTLR .ANTLR предоставил мне грамматику, которая представлена ​​в виде абстрактного синтаксического дерева AST, как вы только что описали, и сгенерировал код на c #, который может обрабатывать эту грамматику.

Это довольно красиво и элегантно.Вот несколько примеров .