C++表达式树遍历以将表达式更改为NNF

Question

我想把一个表达式转换成否定范式。为此，我有一个使用智能指针的二进制表达式树。问题是，当双否定发生在二进制表达式中时，删除双重否定是行不通的，尽管函数removeDoubleNot()是在正确的时间调用的。因此，例如(A∨‘B)变成了’A∧‘B而不是’A∧B‘，但它只在B上起作用。我猜想这个错误在evaluate()中，但我还找不到它。也许递归是错误的？

// It is assumed that all Expressions are valid
std::shared_ptr<Expression> NNF::removeDoubleNot(std::shared_ptr<Not> expr) {
    // Left is a Not -> remove both Nots
    if (auto node = dynamic_cast<Not *>(expr->getLeft().get()))
        return node->getLeft();
    return expr;
}

std::shared_ptr<Expression> NNF::applyDeMorgan(std::shared_ptr<Not> expr) {
    // And
    if (auto node = dynamic_cast<And *>(expr->getLeft().get())) {
        auto newLeft = std::make_shared<Not>(node->getLeft());
        auto newRight = std::make_shared<Not>(node->getRight());
        return std::make_shared<Or>(newLeft, newRight);
    }
    // Or
    if (auto node = dynamic_cast<Or *>(expr->getLeft().get())) {
        auto newLeft = std::make_shared<Not>(node->getLeft());
        auto newRight = std::make_shared<Not>(node->getRight());
        return std::make_shared<And>(newLeft, newRight);
    }
    return expr;
}

std::shared_ptr<Expression> NNF::removeImplication(const std::shared_ptr<Implication> &expr) {
    auto newLeft = std::make_shared<Not>(expr->getLeft());
    auto newRight = expr->getRight();
    return std::make_shared<Or>(newLeft, newRight);
}

std::shared_ptr<Expression> NNF::moveNegationInwards(const std::shared_ptr<Not> &notExpr) {     
    expr = applyDeMorgan(node);
    if (auto node = std::dynamic_pointer_cast<Not>(expr))
        expr = removeDoubleNot(node);
    return expr;
}

std::shared_ptr<Expression> NNF::evaluate(std::shared_ptr<Expression> expr) {
    if (expr == nullptr)
        return nullptr;
    // Implication
    if(auto node = std::dynamic_pointer_cast<Implication>(expr)){
        auto ret = removeImplication(node);
        evaluate(ret->getLeft());
        evaluate(ret->getRight());
        return ret;
    }
    // Other binary than implication
    if(auto node = dynamic_cast<Binary*>(expr.get())){
        evaluate(node->getLeft());
        evaluate(node->getRight());
        return expr;
    }
    // Not
    if(auto node = std::dynamic_pointer_cast<Not>(expr)) {
        auto ret =  moveNegationInwards(node);
        evaluate(ret->getLeft());
        evaluate(ret->getRight());
        return ret;
    }
    return expr;
}

Answer 1

当您调用evaluate(ret->getLeft())时，您没有使用返回值，因此您永远不会更改当前的子表达式。因此，您需要将其更改为：

ret->setLeft(evaluate(ret->getLeft()));

对的也是一样。

您可能想要考虑使用[[nodiscard]]来获得类似错误的编译器警告。