ottiene elementi in "AND" nella stringa logica con Python

Question

Voglio analizzare le stringhe logiche e ottenere tutte le combinazioni di elementi che si trovano in una logica "e". Ad esempio, per la stringa '(A e (B o C))' Dovrei ottenere [[A, B], [A, C]] e per la stringa '(A e B e (C o D e F) o F e G) 'Dovrei ottenere [[A, B, C], [A, B, D, F], [F, G]].

Sto provando ad usare il pyparsing. A seguito di questo post qui parsing a complex logical expression in pyparsing in a binary tree fashion riesco a ottenere un elenco nidificato con le lettere raggruppati in base alle preferenze ("e" ha la preferenza su "o", e tra parentesi le sostituzioni questo):

import pyparsing as pp 

complex_expr = pp.Forward() 
vars = pp.Word(pp.alphas, pp.alphanums + "_") | pp.Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?").setName('proteins') 
clause = pp.Group(vars^(pp.Suppress("(") + complex_expr + pp.Suppress(")"))) 

expr = pp.operatorPrecedence(clause,[ 
          ("and", 2, pp.opAssoc.LEFT,), 
          ("or", 2, pp.opAssoc.LEFT,),]) 
#print expr 
complex_expr << expr 
parseresult=complex_expr.parseString('(A and B and (C or D and F) or F and G)') 
print parseresult 

Che dà:

[[[['A'], 'and', ['B'], 'and', [['C'], 'or', [['D'], 'e' , [ 'F']]]]], 'o', [[ 'F'], 'e', ​​[ 'G']]]]]

Ora come posso elaborare questo risultato per ottenere l'output desiderato? Sarei grato per qualsiasi aiuto. Ho provato il pyparsing ma sono aperto ad altri moduli che potrebbero essere migliori.

Grazie in anticipo.

Answer 1

librerie Python stanno per aiutarci un po ':

import re 
import itertools 

Scriviamo la funzione richiesta:

def analyse(expression): 
    # Find all used symbols 
    symbols = set(re.findall(r"\b[A-Z]\b", expression)) 
    # Find all combinations of symbols and values 
    mappings = (dict(zip(symbols, values)) for values in itertools.product([False, True], repeat=len(symbols))) 
    # Select combinations that make the whole expression true 
    solutions = [sorted(name for name in mapping if mapping[name]) for mapping in mappings if eval(expression, None, mapping)] 
    # Filter out redundant solutions 
    return sorted(s1 for s1 in solutions if not any(set(s1) > set(s2) for s2 in solutions)) 

E cerchiamo di testarlo:

assert analyse("(A and (B or C))") == [["A", "B"], ["A", "C"]] 
assert analyse("(A and B and (C or D and F) or F and G)") == [["A", "B", "C"], ["A", "B", "D", "F"], ["F", "G"]] 

Non ci sono commenti nel codice sorgente. In ogni caso, i passaggi principali sono:

• Le variabili di espressione si trovano come nomi maiuscoli a singolo carattere.
• Ogni variabile può essere Vero o Falso. Troviamo tutte le combinazioni.
• Selezioniamo solo tali combinazioni che rendono l'intera espressione Vero.
• Manteniamo solo soluzioni minime, ad esempio quelle che non sono superserie di altre soluzioni.

Desidero ringraziarvi per una bella domanda. Il Python itertools non smette mai di sorprendermi. ;-)