Генерация булевского выражения
Добавлено: 28 июл 2009, 18:00
Ищу алгоритм или хотя-бы идею алгоритма для ршения следующей задачи:
На входе имеется дерево, у которого листья – булвские переменные(могут повторяться), а остальные вершины – булевские операторы типа AND, OR, NOT OR, XOR и тп.
Мне надо свернуть это дерево в вырожение, содержащее только AND, OR и NOT.
К сожалению подходящий стандартный алгоритм мне неизвестен.
На первый взгляд сам алгоритм не представляется очень сложным:
- рекурсия сверху вниз
- наверх поступает выражение как бы в скобках
- раскрытие скобок
Проблема возникает при возрастании размерностей.
В данный момент у меня основная проблема с оператором AND.
Алгоритм примитивный – реализует декартого произведение термов и представляет из себя 3 вложенных цикла:
Первый – перебор термов в первом операнде
Второй – перебор термов в втором операнде
Третий – перемножение двух текущих термов.
При размерностях выражений в сотни тысяч термов машина засыпает напрочь.
Буду рад любым идеям.
На входе имеется дерево, у которого листья – булвские переменные(могут повторяться), а остальные вершины – булевские операторы типа AND, OR, NOT OR, XOR и тп.
Мне надо свернуть это дерево в вырожение, содержащее только AND, OR и NOT.
К сожалению подходящий стандартный алгоритм мне неизвестен.
На первый взгляд сам алгоритм не представляется очень сложным:
- рекурсия сверху вниз
- наверх поступает выражение как бы в скобках
- раскрытие скобок
Проблема возникает при возрастании размерностей.
В данный момент у меня основная проблема с оператором AND.
Алгоритм примитивный – реализует декартого произведение термов и представляет из себя 3 вложенных цикла:
Первый – перебор термов в первом операнде
Второй – перебор термов в втором операнде
Третий – перемножение двух текущих термов.
При размерностях выражений в сотни тысяч термов машина засыпает напрочь.
Буду рад любым идеям.