Convert Or(And) logical statements to And(Or) statements-CodePudding

Suppose we have these comparison operators:

export enum ComparisonOperators {
   MATCH_CONTAINS = 'contains',
   MATCH_DOES_NOT_CONTAIN = 'not_contains',
   MATCH_EQUALS = 'equals',
   MATCH_NOT_EQUALS = 'not_equals',
   MATCH_STARTS_WITH = 'starts_with',
   MATCH_DOES_NOT_START_WITH = 'not_starts_with',
   MATCH_ENDS_WITH = 'ends_with',
   MATCH_DOES_NOT_END_WITH = 'not_ends_with',
   MATCH_REGEX = 'matches_regex',
   DOES_NOT_MATCH_REGEX = 'not_matches_regex',
}

And suppose we have this Or(And) logical statement in a Json format:

{
   nodeType: 'OR',
   children: [
     {
        nodeType: 'AND',
        children: [
            {
              operator: ComparisonOperators.MATCH_EQUALS,
              field: 'A',
              nodeType: 'LEAF',
              value: 'abc',
            },
            {
              operator: ComparisonOperators.MATCH_STARTS_WITH,
              field: 'B',
              nodeType: 'LEAF',
              value: 'rfg',
            },
        ],
     },
     {
        nodeType: 'AND',
        children: [
            {
              operator: ComparisonOperators.MATCH_DOES_NOT_END_WITH,
              field: 'C',
              nodeType: 'LEAF',
              value: 'esa',
            },
            {
              operator: ComparisonOperators.MATCH_REGEX,
              field: 'D',
              nodeType: 'LEAF',
              value: '/[0-9]{4}/.source',
            },
        ],
     },
   ],
}

Meaning (in simple language):

('A' equals 'abc' AND 'B' startsWith 'rfg') OR ('C' doesNotEndWith 'esa' AND 'D' matchRegex '/[0-9]{4}/.source')

I need to create an algorithm to convert

OR(AND) = (-- AND -- AND ...) OR (-- AND -- AND ...) OR ...

AND(OR) = (-- OR -- OR ...) AND (-- OR -- OR ...) AND ...

And vice versa

Converting AND(OR) to OR(AND) is easy => (a b) * (c d) = a*c a*d b*c b*d

But I can't find how to do the reverse ?

CodePudding user response：

As you pointed out, (a b) * (c d) = a*c a*d b*c b*d.
You said you cannot find how to do the inverse. So let's think about why the above statement is true.

This is because the following holds:
(a b) * c = a*c b*c. Thus, (a b) * (c d) = a*(c d) b*(c d) = a*c a*d b*c b*d.

But keep in mind, that we are not operating on addition and multiplication, but on logical AND and OR operations. This means that perhaps, not only AND distributes over OR, but maybe OR distributes over AND.

Indeed it is true, that (a*b) c = a c * b c. (Can you see why? If not, simply consider all 8 possibilities.

Thus it follows, that (a*b) (c*d) = a c * a d * b c * b d. So in fact, you can do exactly the same thing you already mentioned, but with the operations flipped. Isn't that neat?

Now this means, that converting from AND(OR) to OR(AND) and then back to AND(OR) will very likely result in a much longer output than the original input, but reducing the length of this output is probably a very hard problem to solve algorithmically and I doubt is required in your task.