Как улучшить приведенный ниже алгоритм преобразования CNF в DNF, чтобы распределить более одного дизъюнкции - PullRequest
Новая
       87

Как улучшить приведенный ниже алгоритм преобразования CNF в DNF, чтобы распределить более одного дизъюнкции

0 голосов
/ 28 марта 2020

Код принимает узел AST root, представляющий CNF, и преобразует его в DNF. Я использовал алгоритм Shunting Yard для построения AST из выражения CNF.

Когда у меня есть выражение, как показано ниже: 

(A OR B) AND (C OR D)

Я получаю следующее: 

A AND C OR B AND C OR A AND D OR B AND D

Но когда У меня есть следующее: 

(A OR B) AND (C OR D OR E)

Я получаю это: 

A AND C OR B AND C OR A AND (D OR C) OR B AND (D OR C)

Ниже приведен код, который я написал: 

private static void distributeExpression(ASTNode astNode) {

        if (astNode.getLeft() != null) {
            distributeExpression(astNode.getLeft());
        }
        if (astNode.getRight() != null) {
            distributeExpression(astNode.getRight());
        }

        if ("AND".equals(astNode.getValue())) {
            ASTNode leftOR = null;
            ASTNode rightOR = null;
            ASTNode and = null;
            Deque<ASTNode> node = new ArrayDeque<ASTNode>();

            ASTNode left = astNode.getLeft();
            ASTNode right = astNode.getRight();

            if ("OR".equals(left.getValue())) {
                leftOR = left;
            } else {
                and = left;
            }
            if ("OR".equals(right.getValue())) {
                rightOR = right;
            } else {
                and = right;
            }

            if (and == null) {
                node.push(new ASTNode("AND", leftOR.getLeft(), rightOR.getLeft()));
                node.push(new ASTNode("AND", leftOR.getRight(), rightOR.getRight()));

                node.push(new ASTNode("AND", leftOR.getLeft(), rightOR.getRight()));
                node.push(new ASTNode("AND", leftOR.getRight(), rightOR.getLeft()));
            } else {
                if (rightOR == null) {
                    node.push(new ASTNode("AND", leftOR.getRight(), and));
                    node.push(new ASTNode("AND", leftOR.getLeft(), and));
                } else {
                    node.push(new ASTNode("AND", rightOR.getRight(), and));
                    node.push(new ASTNode("AND", rightOR.getLeft(), and));
                }
            }

            while (node.size() > 1) {
                node.push(new ASTNode("OR", node.pop(), node.pop()));
            }

            ASTNode astNode2 = node.pop();
            astNode.setValue(astNode2.getValue());
            astNode.setRight(astNode2.getLeft());
            astNode.setLeft(astNode2.getRight());
        }
    }

PS: я следовал упомянутому алгоритму в ответ. [ Применить закон о распределении по AST (или RPN) => дизъюнктивная нормальная форма

...