Требуется руководство к оценочному булевому логическому дереву

Question

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

Проблема в том, что мне нужен способ фильтрации данных в том, что я могу назвать только составным логическим деревом. В настоящее время система реализует простую систему фильтрации AND. Например, допустим, у нас есть набор данных людей. Вы добавляете несколько фильтров, которые показывают всем людям, где (Пол = Женщина) И (Возраст> 23) И (Возраст <30) И (Статус = Одинокий). Достаточно просто, перебирать каждый элемент, добавлять в допустимую коллекцию элементов, только если каждое условие выполняется. </p>

Проблема, с которой я сталкиваюсь, заключается в том, как мне справиться с тем, что пользователь может создавать сложные запросы, и / или или? Я имею в виду что-то вроде дерева, где каждый узел представляет, а выражение оценивает его потомков как true или false. В качестве упрощенного примера можно привести фильтр ((Пол == Мужчина И Возраст == 25) ИЛИ (Пол == Женский И Статус == Одинокий)) И IQ> 120. Извините, я не могу придумать лучшего примера в момент Но как бы вы представили дерево выражений такого типа и оценили элементы в коллекции по этим фильтрам? Какие ссылки могут помочь? Черт, что за чертов поиск в Google может привести к положительному направлению?!

Спасибо всем, кто может оказать любую помощь.

Вот пример составного запроса в древовидной форме с использованием набора данных людей

• Запрос - Покажите мне всех людей, где секс мужской или глаза зеленые или женский, глаза голубые или одинокий статус. В паренской форме (Секс == Мужской && Глаза == Зеленый) || (Секс == Женский && (Глаза == Синий || Статус == Одинокий))

Так в древовидной форме я думаю

o-Root Node
  - And - Sex = Male
     - And - Eyes = Blue
  - Or - Sex = Female
     - And Eyes = Blue
     - Or Status = Single

Я полагаю, что решение состоит в том, чтобы представить каждый узел, такой в ​​структуре данных, как

Node
{
   OpType - AND or OR
   ExpressionField - The field to evaluate
   ExpressionOp -   =, !=, >, >=, <, <=
   ExpressionValue - the value to compare the field's value against

   Function Evaluate() - returns a bool
}

Таким образом, для данного узла оцените детей, если вы являетесь узлом AND, а затем верните true, если ваше выражение приводит к true, а все ваши дочерние элементы AND оцениваются как true или любой дочерний элемент OR оценивается как true и повторяется. *

Кажется, что удовлетворяет каждому концептуальному условию, которое я могу бросить, но мы сделаем это, как только я его осуществлю. Я опубликую реальный код позже, когда он будет работать, и картинки, чтобы лучше описать эту проблему для других.

Answer 1

Вы можете использовать Google для таких терминов, как «исчисление предикатов» и «нормальная конъюнктивная форма».

Answer 2

Эти типы запросов часто представлены как OR ed массив AND ed предложений. То есть табличный формат, в котором вы читаете в нескольких условиях AND и редактируете их вместе, а затем читаете их до OR. Это приводит к некоторому повторению условий, но пользователям легко читать, писать и понимать. Ваш образец ((Sex == Male AND Age == 25) OR (Sex == Female AND Status == Single)) AND IQ > 120 будет выглядеть как

Sex == Male   & Age == 25        & IQ > 120 
Sex == Female & Status == Single & IQ > 120 

Answer 3

Ваш анализ выражения ((Пол == Мужчина И Возраст == 25) ИЛИ (Пол == Женский И Статус == Одинокий)) И IQ> 120 выглядит странно. Я бы разобрал это как:

* And
    * Or
        * And
            * ==
                * Sex
                * Male
            * ==
                * Eyes
                * Blue
        * And
            * ==
                * Sex
                * Female
            * ==
                * Status
                * Single
    * >
        * IQ
        * 120

Тип дерева будет:

Node
{
    bool evaluate ()
}

AndNode : Node
{
    Node left
    Node right

    bool evaluate ()
    {
        return left.evaluate () && right.evaluate ()
    }
}

// OrNode is similar

EqualsNode : Node
{
    Field field
    Value value

    bool evaluate ()
    {
        return field.value () == value
    }
}

// Likewise for <, >, etc

Answer 4

Похоже, вам нужно создать пользовательский интерфейс, который позволяет создавать простое дерево разбора. Когда вы нажимаете GO, вы можете пройтись по дереву и создать дерево выражений LINQ из этой структуры пользовательского интерфейса. Выполните запрос LINQ, а затем обработайте результаты по мере необходимости. Поэтому я бы рекомендовал вам ознакомиться с деревьями выражений LINQ.

Answer 5

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