需要有关评估布尔逻辑树的指导

Question

我似乎无法找到正确方向的指针,我甚至不确定我应该研究的条款是什么,但无数小时的谷歌搜索似乎在旋转我的圈子,所以希望堆栈智能的集体蜂巢溢出可以帮助.

问题是,我需要一种方法来过滤数据,我只能称之为复合逻辑树.目前,该系统实现了一个简单的AND过滤系统.例如,假设我们有一个人的数据集.你添加了一堆过滤器,显示所有人(性别=女性)和(年龄> 23)AND(年龄<30)和(状态=单身).很容易,遍历每个项目,只有在每个条件都为真时才添加到有效的项目集合.

我遇到的问题是如何处理用户能够构建涉及的复杂查询和/或？我正在考虑像每个节点所代表的树和表达式,将其子节点评估为真或假.一个简单的例子是 - 过滤到((性别= =男性和年龄= = 25)或(性别==女性和状态==单身))和智商> 120.对不起我想不出一个更好的例子在此时此刻.但是,您将如何表示此类型的表达式树,并针对这些过滤器评估集合中的项目.有哪些参考资料会有所帮助？天啊,谷歌搜索什么可能会导致一个积极的方向？!

感谢任何可以提供任何帮助的人.

以下是使用人员数据集的树形式的复合查询示例

• 查询 - 告诉我所有性别为男性,眼睛是绿色或性别是女性,眼睛是蓝色,或状态是单身的人.以Paren形式(性别= =男性&&眼睛==绿色)|| (性别==女性&&(眼睛==蓝色||状态==单身))

所以在树形式即时思考

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节点,则评估chilren,如果表达式结果为true且所有AND子项计算为true或任何OR子计算结果为true并递归,则返回true.

似乎满足了我可以抛出的每一个概念条件,但是一旦我实现它,我们就会这样做.我将在以后的工作和图片上发布真实代码,以帮助更好地描述其他人的问题.

Answer 1

您对表达式 ((Sex == Male AND Age == 25) OR (Sex == Female AND St​​atus == Single)) AND 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