Conversion d'une expression en forme normale conjonctive avec une torsion

Question

J'ai une bibliothèque avec laquelle je dois m'interfacer et qui agit essentiellement comme une source de données. Lors de la récupération des données, je peux passer des "expressions de filtre" spéciales à cette bibliothèque, qui sera ensuite traduite en partie SQL WHERE. Ces expressions sont assez limitées. Ils doivent être en forme normale conjonctive. Comme:

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

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

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

obtiendraient 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 la bibliothèque Irony. Maintenant, je dois normaliser, mais je ne sais pas comment ... Oh,, voici aussi 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 par 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 à une SQL instruction WHERE pratiquement identique, une instruction complexe ralentirait donc très probablement la vitesse d'exécution.

Answer 1

J'utiliserais deux itérations sur l'arbre, bien que ce soit probablement possible dans un.

Première itération: débarrassez-vous de vos NOT NOT en traversant l'arbre et en utilisant la loi de De Morgan (wikipedia link) et enlevez la double négation, le cas échéant.

deuxième itération (NOT sont maintenant seulement directement avant un nœud feuille) Passez par 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 devriez faire.