如何在JSON树结构中建模布尔表达式

Question

我在谷歌和stackoverflow上花了几个小时，但我仍然没有找到如何建模嵌套的布尔数据的结论。

假设我有以下表达式：

123 and 321 and (18 or 19 and (20 or 21))

如何用JSON树结构建模，以便通过遍历树来重建与上面所示相同的表达式？ 我不需要实际评估逻辑，而只需以呈现逻辑的树形方式构造它即可。

事先感谢您。

记录一下，我正在尝试完成的系统类型以及根据下面的答案猜测树应该如何结构化。

ANY OF THESE:
    13
    14
    ALL OF THESE:
        18
        19
        20

          or
        /   \
       or   13
      /  \
    14    and
         /   \
       and   18
       / \
     20   19

- ThinkingInBits

---

值得注意的是，问题和答案似乎与JSON无关。是的，讨论将逻辑建模为树形结构，但接受的答案中没有提到JSON。也许应该更新问题，只是将其描述为“将逻辑建模为抽象树”。 - thom_nic

Answer 1

我的ConditionSet以JSON格式为：

"FilterCondition": {
  "LogicalOperator": "AND",
  "Conditions": [
    {
      "Field": "age",
      "Operator": ">",
      "Value": "8"
    },
    {
      "LogicalOperator": "OR",
      "Conditions": [
        {
          "Field": "gender",
          "Operator": "=",
          "Value": "female"
        },
        {
          "Field": "occupation",
          "Operator": "IN",
          "Value": ["business","service"]
        }
      ]
    }
  ]
}

参考链接：https://zebzhao.github.io/Angular-QueryBuilder/demo/

- swarnim gupta

---

这是对楼主问题的回答吗？ - mishsx

Answer 2

考虑编程语言对语句部分进行评估的顺序。根据and和or的优先级以及它们的左或右关联性，它必须选择一些最“深”的部分并首先对其进行评估，然后将其作为完全评估的操作数之一提供给其“父”（最接近的较少关联运算符），然后当该操作数被评估时，它有一个父母等等。

因此，您将拥有一棵树，在完全评估后到达根节点，并且叶节点是可以首先评估的表达式部分（不依赖于任何评估来获得其结果）。

以简单的例子1 and (2 OR 3)为例，模型如下：

  and
 /   \
1    or
    /  \
   2    3

如果同一优先级的运算符从左到右进行求值，并且AND的优先级高于OR（例如C ++中的true：http://en.cppreference.com/w/cpp/language/operator_precedence），那么

123 and 321 and (18 or 19 and (20 or 21))

变成

        and
       /   \
    and     \
   /   \     \
123     321   \
               \
                or
               /  \
             18    and
                  /   \
                or     19
               /  \
             20    21

为了评估这棵树的结果，你需要首先评估最深层的节点，用其当前的运算符替换每个节点及其左右子节点的计算结果，直到根节点只剩一个数字。

要将布尔表达式转换成布尔表达式树，您需要编写一个解析器*，例如在Python中，您可以使用PLY http://www.dabeaz.com/ply/编写它。每种语言都有不同的第三方解析器构建库，最受欢迎的也各不相同。

- Patashu

---

你能提供一个示例，其中有多个并列的and运算符在同一级别上吗？也许可以使用我上面的示例。 - ThinkingInBits

你怎么知道括号放在哪里？ - ThinkingInBits

如果你是指编程方面，你需要编写一个解析器（查看 PLY 的文档，它专门用于编写表达式、语法等解析器，你会了解到它的工作原理和为什么必须这样做）。不要试图在没有解析器的情况下完成。 - Patashu

@ThinkingInBits，您能否编辑您的问题以明确您想要什么？ - Patashu

@ThinkingInBits 不小心点击了“移至聊天”链接。那看起来是正确的。 - Patashu