как преобразовать логическое дерево высказываний в дерево нормальной формы соединения (CNF)

Question

как преобразовать логическое дерево высказываний в дерево нормальной формы соединения (CNF)

У меня есть строка как строка

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

и преобразовать его, выводит CNF этой строки, как

(ИЛИ (НЕ Р) (ИЛИ Б)
(ИЛИ (НЕ Р) (ИЛИ (НЕ Б) (НЕ А)))

мне нужно сделать структуру 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

c++conjunctive-normal-form prefix-tree recursion

Решение

Другие решения

Простое решение парсера рекурсивного спуска:

TreeNode* ParseExpression(const char*& p): Если строка, на которую указывает p, не начинается с ‘(‘, тогда возвращает ParseAtom (p), иначе передвиньте p за ‘(‘, вызовите ParseOperation (p), затем передвиньте p за ‘) и верните возвращенное значение ParseOperation.

TreeNode* ParseAtom(const char*& p): пропустить p мимо атома (непрерывный ряд непространств). Вернуть TreeNode с атомом в качестве значения и NULL влево и вправо.

TreeNode* ParseOperation(const char*& p): Строка, на которую указывает p, должна начинаться с оператора. Переместите p мимо оператора, затем определите, сколько операндов занимает оператор. Если один, Вызовите ParseExpression (p) один раз; если два, вызовите ParseExpression (p) дважды. Затем верните TreeNode с оператором в качестве значения и результаты одного или двух вызовов ParseExpression как левый и правый (право должно быть NULL для оператора с одним операндом).

Установить указатель, указывающий на исходную строку; вызовите ParseExpression для этого указателя; возвращаемое значение — ваше дерево, и указатель будет указывать после первого выражения в вашей строке.

Это отвечает на один из ваших вопросов: как превратить строку в дерево. Адриан Панасюк обратился к другому вопросу, как преобразовать дерево в нормальную форму. Так как вы собираетесь делать дополнительные преобразования дерева, «значение» в ваших узлах должно называться «op» или что-то подобное, что означает «оператор» (это зарезервированное слово в C ++), и это должно быть перечисление , а не строка.

2

Источник

Accepted Answer

Допустим, вы называете свою функцию CNF, беря дерево и возвращая дерево в CNF.

Сначала замените эквивалентность p<=>q с AND(p=>q,q=>p) затем заменить последствия p=>q с OR(q,NOT(p)),
Преобразовать в отрицание нормальную форму: переместить все NOT операции вниз по дереву, так что NOT операции связываются только с атомами (A, B).
Тогда результат CNF(AND(x,y)) это просто: AND(CNF(x),CNF(y))так как это похоже на CNF ANDвысоко в дереве.
Результат 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)),

И вы сделали.

4