Преобразование выражения в конъюнктивную нормальную форму с изюминкой

У меня есть библиотека, с которой я должен взаимодействовать, которая действует в основном как источник данных. При извлечении данных я могу передать в эту библиотеку специальные «выражения фильтра», которые позже будут преобразованы в часть SQL WHERE. Эти выражения довольно ограничены. Они должны быть в конъюнктивной нормальной форме. Нравиться:

(A or B or C) and (D or E or F) and ...

Это, конечно, не очень удобно для программирования. Итак, я хочу сделать небольшую оболочку, которая может анализировать произвольные выражения и переводить их в эту нормальную форму. Нравиться:

(A and (B or C) and D) or E

будет переведено на что-то вроде:

(A or E) and (B or C or E) and (D or E)

Я могу преобразовать выражение в дерево с помощью библиотеки Irony. Теперь мне нужно его нормализовать, но я не знаю, как... Ах, вот еще поворот:

  • Окончательное выражение не может содержать оператор NOT. Однако я могу обратить отдельные члены, заменив операторы обратными операторами. Итак, это нормально:

    (not A or not B) AND (not C or not D)

    но это не так:

    not (A or B) and not (C or D)

  • Я хотел бы сделать выражение как можно более простым, потому что оно будет переведено в практически идентичный оператор SQL WHERE, поэтому сложный оператор, скорее всего, замедлит скорость выполнения.

expression conjunctive-normal-form
person Vilx-    schedule 18.05.2009    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Я бы использовал две итерации по дереву, хотя, вероятно, это возможно и за одну.

Первая итерация: избавьтесь от узлов НЕ, пройдясь по дереву и используя закон Де Моргана (ссылка на википедию) и удалите двойное отрицание, где это применимо.

Вторая итерация (НЕ теперь только непосредственно перед конечным узлом) Пройдите через свое дерево:

Case "AND NODE":
    fine, inspect the children
Case "OR NODE":
    if there is a child which is neither a Leaf nor a NOT node
        apply the distributive law.
        start from parent of current node again
    else
        fine, inspect children

После этого вы должны быть сделаны.

person HerdplattenToni    schedule 18.05.2009
comment
Хех, я сам почти приехал туда. :) - person Vilx-; 18.05.2009