Have Geek Brain

Convert an expression to conjunctive normal form with swirl

I have a library that I have to interact with which acts mainly as a data source. When I receive data, I can pass special "filter expressions" to this library, which will later be translated into the SQL WHERE part. These expressions are rather limited. They must be in conjunctive normal form. How:

(A or B or C) and (D or E or F) and ...

This, of course, is not very convenient for programming. So I want to create a little wrapper that can parse arbitrary expressions and translate them into this normal form. How:

(A and (B or C) and D) or E

would translate to something like:

(A or E) and (B or C or E) and (D or E)

I can parse the tree expression using the Irony library . Now I need to normalize it, but I don't know how ... Oh, also, here's the twist:

  • The final expression cannot contain the NOT operator . However, I can invert individual members by replacing the operators with inverse operators. So that's okay:

    (not A or not B) AND (not C or not D)



    but it isn't:

    not (A or B) and not (C or D)



  • I would like to keep the expression as simple as possible, because it will translate to a nearly identical SQL WHERE clause, so a complex statement will likely slow down execution speed.
+1


a source to share


1 answer


I would use two iterations over the tree, although this is possible in one.

First iteration: get rid of your NOT nodes by walking through the tree and using De Morgan's law ( wikipedia link ) and remove double negation where applicable.

Second iteration (NOT now just immediately before the leaf node) Go through your tree:



Case "AND NODE":
    fine, inspect the children
Case "OR NODE":
    if there is a child which is neither a Leaf nor a NOT node
        apply the distributive law.
        start from parent of current node again
    else
        fine, inspect children

Then you have to do.

+2


a source






More articles:


All Articles