Разворачивания логического утверждения (перемножения)

Question

Ищу способ расширить логическое выражение (в виде строки) формы:

«(А или В) и ((C и D) или E)»

в Python, чтобы получить список всех положительных наборов, т.е.

['A and C and D', 
'A and E', 
'B and C and D', 
'B and E'] 

, но я не смог найти, как это сделать. Я исследовал pyparser, но я не могу решить, какой пример имеет значение в этом случае. Это может быть очень легко с какой-то логической манипуляцией, но я не знаю никакой формальной логики. Любая помощь или ссылка на ресурс, который может помочь, будут очень признательны.

Answer 1

Вот бит пиперации, взятый из примера SimpleBool.py. Во-первых, использовать infixNotation (ранее известный как operatorPrecedence), чтобы определить грамматику выражение, которое поддерживает вводную группировку, и признает приоритет операций:

from pyparsing import * 

term = Word(alphas) 

AND = Keyword("and") 
OR = Keyword("or") 

expr = infixNotation(term, 
    [ 
    (AND, 2, opAssoc.LEFT), 
    (OR, 2, opAssoc.LEFT), 
    ]) 

sample = '(A or B) and ((C and D) or E)' 

result = expr.parseString(sample) 

from pprint import pprint 
pprint(result.asList()) 

печатает:

[[['A', 'or', 'B'], 'and', [['C', 'and', 'D'], 'or', 'E']]] 

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

Далее мы добавляем действия синтаксического анализа на каждый уровень иерархии операций. Для разбора действий здесь, мы на самом деле проходят занятия, так что вместо выполнения функций и возвращает некоторое значение, анализатор будет вызывать конструктор класса и инициализатору и возвращает экземпляр класса для конкретного подвыражения:

class Operation(object): 
    def __init__(self, tokens): 
     self._tokens = tokens[0] 
     self.assign() 

    def assign(self): 
     """ 
     function to copy tokens to object attributes 
     """ 

    def __repr__(self): 
     return self.__class__.__name__ + ":" + repr(self.__dict__) 
    __str__ = __repr__ 

class BinOp(Operation): 
    def assign(self): 
     self.op = self._tokens[1] 
     self.terms = self._tokens[0::2] 
     del self._tokens 

class AndOp(BinOp): 
    pass 

class OrOp(BinOp): 
    pass 

expr = infixNotation(term, 
    [ 
    (AND, 2, opAssoc.LEFT, AndOp), 
    (OR, 2, opAssoc.LEFT, OrOp), 
    ]) 

sample = '(A or B) and ((C and D) or E)' 

result = expr.parseString(sample) 
pprint(result.asList()) 

возвращений:

[AndOp:{'terms': [OrOp:{'terms': ['A', 'B'], 'op': 'or'}, 
        OrOp:{'terms': [AndOp:{'terms': ['C', 'D'], 
            'op': 'and'}, 'E'], 'op': 'or'}], 
'op': 'and'}] 

Теперь, когда выражение было преобразовано в структуру данных подвыражений, я оставляю вам, чтобы сделать работу по добавлению методов к AndOp и OrOp генерировать различные комбинации терминов, которые будут оценивать в целом на True. (Посмотрите на логику в примере invregex.py, который инвертирует регулярные выражения для идей о том, как добавлять функции генератора в анализируемые классы, чтобы генерировать различные сочетания терминов, которые вы хотите.)

Answer 2

Звучит так, как будто вы хотите преобразовать эти выражения в Disjunctive Normal Form. Канонический алгоритм для этого - алгоритм Куайна-Маккласки; вы можете найти некоторую информацию о реализации Python в соответствующем Wikipedia article и в ответах на this SO question.