Conversion en CNF

Question

Ceci est pour une affectation. Je dois convertir l'ensemble d'instructions en CNF et les implémenter. Je sais que j'ai besoin de convertir l'entrée en notation de préfixe pour infixer d'abord, puis appliquer à plusieurs reprises les lois de De Morgans. Cependant, je ne sais pas comment procéder avec l'implémentation après la conversion en notation infixe.

1. Dois-je le convertir en infixe ou existe-t-il un meilleur processus pour le faire?
2. J'ai lu sur les BDD de l'implémentation en Python here. Je code en Java et j'aimerais le faire moi-même sans utiliser de bibliothèque externe. Des pointeurs sur l'algorithme d'implémentation? Est-ce que je vais dans la bonne direction pour le convertir en infixe?

Merci!

Answer 1

Il n'y a pas besoin de convertir en infix - vous voulez sortir du domaine des chaînes aussi rapidement que possible, par exemple

public abstract class Expression 
public abstract class BinaryExpression extends Expression { 
    private Expression expr1; 
    private Expression expr2; 
    public Expression getExpr1() { return expr1; } 
    public void setExpr1(Expression expr) { expr1 = expr; } 
} 
public abstract class UnaryExpression extends Expression 
public class Or extends BinaryExpression 
public class Not extends UnaryExpression 

et ainsi de suite. Pour analyser l'entrée dans Expressions, vous pouvez trouver utile d'utiliser un Recursive Descent Parser, bien que ce ne soit certainement pas la seule façon d'analyser votre entrée. Une fois que vous avez converti votre entrée en un format symbolique Expression, il devrait être beaucoup plus facile d'appliquer les lois booléennes pour le convertir en CNF.