У меня есть строка как строка
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, который в нормальной форме соединительный?
пожалуйста, дайте некоторые подробности алгоритма.
С моей точки зрения, возможно, для решения этой проблемы лучше использовать рекурсивную функцию, но я до сих пор не могу придумать, как использовать рекурсию. Или у вас есть другие предложения для решения этой проблемы?
Допустим, вы называете свою функцию 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))
,
И вы сделали.
Простое решение парсера рекурсивного спуска:
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 ++), и это должно быть перечисление , а не строка.