3

I've spent a few hours on google and stack overflow, but I'm yet to come to a conclusion on just how to model nested boolean data.

Let's say I have the following expression:

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

How could I model this in a JSON tree structure so that I could rebuild the expression as you see it above by simply traversing the tree? I don't need to actually evaluate the logic, but simply structure it in such a way that it portrays the logic in tree-form.

Thanks in advance.

For the record, this is the type of system I'm trying to accomplish and how I'm guessing the tree should be structured based on the answer below.

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

          or
        /   \
       or   13
      /  \
    14    and
         /   \
       and   18
       / \
     20   19
1
  • Worth noting that the question and answer seem to have nothing to do with JSON. Yes the discussion of modeling logic as a tree but JSON in the accepted answer. Maybe the question should be updated to just be "model logic as an abstract tree."
    – thom_nic
    Nov 8, 2017 at 17:23

2 Answers 2

4

My ConditionSet in json format :

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

Reference : https://zebzhao.github.io/Angular-QueryBuilder/demo/

1
  • Is that an answer to OPs question?
    – shuberman
    Jul 14, 2020 at 12:12
3

Think about which order the programming language would evaluate the parts of your statement in. Depending on the precedence of and and or and their left or right associativity, it will have to pick some part that is the 'deepest' and it must be evaluated first, then it is given to its 'parent' (the closest less associative operator) as one of its fully evaluated operands, then when that is evaluated it has a parent and so on.

So, you would have a tree where the root is reached after full evaluation, and leaf nodes are the parts of the expression that can be evaluated first (don't rely on any evaluations to come to their result).

As a simple example,1 and (2 OR 3) would be modelled as

  and
 /   \
1    or
    /  \
   2    3

If operators at the same precedence are evaluated left to right and AND is higher precedence than OR (for example true in C++: http://en.cppreference.com/w/cpp/language/operator_precedence ) then

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

becomes

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

And to evaluate the result of this tree, you would evaluate deepest first, replacing each node with the result of evaluating its left and its right with its current operator until there is only one number left in the root.

To go from a boolean expression to a boolean expression tree programatically you need to write a parser*, for example in Python you would write it using PLY http://www.dabeaz.com/ply/ and each language has a different third party parser construction library that is the most popular.

7
  • Could you provide an example with multiple ands at the same level, perhaps using my example from above? May 23, 2013 at 0:43
  • How do you know where the parenthesis are placed? May 23, 2013 at 0:54
  • @ThinkingInBits If you mean programatically, you need to write a parser (look at the documentation for PLY, which is designed to write parsers for expressions, grammars, etc. and you'll see the tricks of how it works and WHY it must work). Don't try to do it without a parser.
    – Patashu
    May 23, 2013 at 1:01
  • The user is actually going to define the logic in the interface through a form that allows them to say "All of these: 1,2,3, Any of these:4,5,6, indent -- all of these 7, 8" May 23, 2013 at 1:03
  • @ThinkingInBits Can you please edit your question to indicate exactly what you want?
    – Patashu
    May 23, 2013 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.