La conversion d'une expression de la forme normale conjonctive avec une torsion

Question

J'ai une bibliothèque que je dois interface avec qui agit essentiellement comme source de données. Lors de la récupération des données, je peux passer « expressions de filtre » spécial à cette bibliothèque, qui se traduit par la suite à SQL WHERE. Ces expressions sont assez limitées. Ils doivent être sous forme normale conjonctive. Comme:

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

Bien sûr, cela n'est pas très confortable pour la programmation. Donc, je veux faire un petit emballage qui peut analyser des expressions arbitraires et de les traduire à cette forme normale. Comme:

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

se serait traduit à quelque chose comme:

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

Je peux analyser une expression à un arbre avec le Irony bibliothèque. Maintenant, je dois normaliser, mais je ne sais pas comment ... Oh, aussi, voici le twist:

• L'expression finale ne peut pas contenir le PAS opérateur. Cependant, je peux inverser les termes individuels en remplaçant les opérateurs avec les opérateurs inverses. Donc, c'est OK:
  (not A or not B) AND (not C or not D)
  mais ce n'est pas:
  not (A or B) and not (C or D)
  
• Je voudrais faire l'expression aussi simple que possible, car il sera traduit à un SQL pratiquement identique instruction WHERE, donc une déclaration complexe serait plus lent probablement vers le bas la vitesse d'exécution.

Answer 1

J'utilise deux itérations sur l'arbre, mais il est probablement possible dans un.

Première itération: se débarrasser de vos noeuds NOT en marchant à travers l'arbre et en utilisant la loi de De Morgan ( lien wikipedia ) et de supprimer la double négation le cas échéant.

Deuxième itération (NOT sont maintenant seulement directement avant un nœud feuille) Allez dans votre arbre:

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

Après que vous devez faire.