改为CNF

Question

这是一项任务。我必须将这组声明转换为CNF，并加以执行。我知道我需要将前缀表示法中的输入转换为先插入，然后反复应用De Morgans定律。但是，我不知道如何在将实现转换为infix表示法之后继续实现。

1. 我是否必须将其转换为infix，或者是否有更好的过程来进行此操作？
2. 我一直在阅读Python的这里实现。我正在用Java编写代码，我想不使用任何外部库就自己编写代码。有关于实现算法的指示吗？我是不是朝正确的方向去把它转换成infix？

谢谢!

Answer 1

没有必要将其转换为infix --例如，您希望尽快摆脱字符串的域。

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

诸若此类。要将输入解析为Expressions，您可能会发现使用递归下降分析器很有用，尽管这肯定不是解析输入的唯一方法。一旦将输入转换为符号Expression格式，应用布尔律将其转换为CNF应该容易得多。