4

我有一个类似字符串的字符串

     s="(=> P (OR (AND A (NOT B)) (AND B (NOT A))))";

并将其转换为输出此字符串的 CNF，例如

（或（非 P）（或 AB））（或（非 P）（或（非 B）（非 A）））

我需要制作一个结构 TreeNode 来保持价值吗？

     struct TreeNode {
            string val;         // The data in this node.
            TreeNode *left;   // Pointer to the left subtree.
            TreeNode *right;  // Pointer to the right subtree.
            //TreeNode *farther;//should I use farther or not in convert to CNF?
      };

如何使其成为合取范式的CNF？请给出一些算法细节。从我的角度来看，也许使用递归函数更好地解决这个问题，但我仍然想不出如何使用递归。或者您有其他解决此问题的建议？

4

2 回答 2

4

假设您为函数命名CNF，取一棵树并在 CNF 中返回该树。

  1. 首先，将等价替换p<=>q为，AND(p=>q,q=>p)然后将蕴涵替换p=>q为OR(q,NOT(p))。

  2. 转换为否定范式：将所有NOT操作向下移动，以便NOT操作仅绑定到原子 ( A, B)。

  3. 然后，结果CNF(AND(x,y))很简单： ，因为在树AND(CNF(x),CNF(y))中有 s 高就像 CNF 。AND

  4. 结果CNF(OR(AND(x,y),z))有点复杂。这里我们将使用析取大于合取的分布规则，它OR(AND(x,y),z)等价于AND(OR(x,z),OR(y,z))。实际上，CNF(OR(AND(x,y),z))将是AND(OR(CNF(x),CNF(z)),OR(CNF(y),CNF(z))。

你完成了。

于 2013-04-18T19:45:20.430 回答
2

简单的递归下降解析器解决方案：

TreeNode* ParseExpression(const char*& p): 如果 p 指向的字符串不是以 '(' 开头，则返回 ParseAtom(p)，否则将 p 移过 '('，调用 ParseOperation(p)，然后将 p 移过 ')' 并返回返回值通过 ParseOperation。

TreeNode* ParseAtom(const char*& p)：跳过 p 过去的原子（连续的非空格系列）。返回一个以原子为值且左右为 NULL 的 TreeNode。

TreeNode* ParseOperation(const char*& p): p 指向的字符串应该以操作符开头。将 p 移过运算符，然后确定运算符需要多少个操作数。如果有，则调用 ParseExpression(p) 一次；如果两个，调用 ParseExpression(p) 两次。然后返回一个 TreeNode，其操作符为值，一两次 ParseExpression 调用的结果为左和右（对于只有一个操作数的操作符，右应为 NULL）。

设置一个指向原始字符串的指针；在该指针上调用 ParseExpression；返回值是您的树，指针将指向字符串中的第一个表达式。

这解决了您的一个问题：如何将字符串变成树。Adrian Panasiuk 解决了另一个问题，即如何将树转换为正常形式。由于您将进行额外的树转换，因此节点中的“值”应该称为“op”或类似的名称来代表“运算符”（这是 C++ 中的保留字），它应该是一个枚举，而不是字符串。

于 2013-04-18T19:50:19.573 回答