java - 转换为 CNF

Question

这是一个作业。我必须将语句集转换为 CNF 并实现它们。我知道我需要先将前缀表示法的输入转换为中缀，然后重复应用 De Morgans 定律。但是，我不知道将其转换为中缀符号后如何继续实现。

1. 我是否必须将其转换为中缀或者是否有更好的流程来执行此操作？
2. 我一直在阅读 Python 实现中的 BDD here .我正在用 Java 编码，我想自己完成而不使用任何外部库。关于实现算法的任何指示？我是否朝着正确的方向将其转换为中缀？

谢谢!

Answer 1

没有必要将其转换为中缀——例如，您想尽快脱离字符串域

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，您可能会发现使用 Recursive Descent Parser 很有用。 ，尽管这肯定不是解析输入的唯一方法。将输入转换为符号 Expression 格式后，应用 boolean 定律将其转换为 CNF 应该会容易得多。