Hai bisogno di una guida verso valutativa albero logica booleana

Question

Non riesco a trovare un puntatore nella direzione giusta, io non sono nemmeno sicuro di quello che i termini sono che io sia ricercando ma innumerevoli ore di googling sembra di me girare in tondo, quindi speriamo che l'alveare collettiva di intelligenza di Stack Overflow può aiutare.

Il problema è questo, ho bisogno di un modo per filtrare i dati in quello che posso solo chiamare un albero logica composto. Attualmente il sistema implementa un sistema semplice e filtraggio. Ad esempio, supponiamo di avere un set di dati di persone. Si aggiunge un sacco di filtri tali che mostrano tutte le persone in cui (sesso = femmina) e (età> 23) e (Età <30) e (Stato = Single). Abbastanza facile, scorrere ogni voce, aggiungere a un insieme di elementi valida solo se ogni condizione è vera.

Il problema che sto incontrando è come faccio a gestire l'utente sia in grado di costruire query complesse coinvolte e di eo di? Sto pensando a qualcosa di simile a un albero in cui ogni nodo rappresenta ed espressione valutare i suoi figli al vero o falso. Un esempio semplice sarebbe - filtrare fino a ((Sesso == maschio e Età == 25) o (sesso femminile e == Stato == singolo)) E IQ> 120. Mi dispiace non posso pensare ad un esempio migliore a il momento. Ma come è possibile fare per rappresentare questo tipo di albero di espressione, e valutare gli elementi in una collezione contro questi filtri. Quali sono alcuni riferimenti che avrebbe aiutato? L'inferno, che cosa sono qualche maledetto Google ricerca che potrebbe portare in una direzione positiva?!

Grazie a tutti coloro in grado di fornire qualsiasi aiuto.

Ecco un esempio di una query composti sotto forma dell'albero utilizzando un set di dati di persone

• Domanda - Mostrami tutte le persone in cui il sesso è maschio e gli occhi sono verdi o il sesso è di sesso femminile, gli occhi sono blu, o lo stato è single. Nella forma Paren (sesso == maschio && Occhi == Verde) || (Sesso == femmina && (Occhi Blu == || Stato == singolo))

In albero forma im pensiero

o-Root Node
  - And - Sex = Male
     - And - Eyes = Blue
  - Or - Sex = Female
     - And Eyes = Blue
     - Or Status = Single

Credo che la soluzione è quella di rappresentare ogni nodo come in una struttura di dati come

Node
{
   OpType - AND or OR
   ExpressionField - The field to evaluate
   ExpressionOp -   =, !=, >, >=, <, <=
   ExpressionValue - the value to compare the field's value against

   Function Evaluate() - returns a bool
}

Quindi, per un dato nodo, valutare i chilren, se sei un e il nodo, per poi tornare vero se i risultati di espressione in un vero e tutti i tuoi e bambini restituiscono true o qualsiasi OR bambino restituisce true e ricorsivamente su.

sembra soddisfare ogni condizione concettuale posso buttare a questo, ma ci sarà in quanto una volta che la sua attuazione. Io posto il codice vero e proprio in un secondo momento, quando il suo funzionamento e le immagini per aiutare a descrivere questo problema meglio per gli altri.

Answer 1

Il tuo analisi dell'espressione ((Sesso == maschio e Età == 25) o (sesso femminile e == Stato == singolo)) E IQ> 120 sembra strano. Vorrei analizzare come:

* And
    * Or
        * And
            * ==
                * Sex
                * Male
            * ==
                * Eyes
                * Blue
        * And
            * ==
                * Sex
                * Female
            * ==
                * Status
                * Single
    * >
        * IQ
        * 120

Il tipo di albero potrebbe essere:

Node
{
    bool evaluate ()
}

AndNode : Node
{
    Node left
    Node right

    bool evaluate ()
    {
        return left.evaluate () && right.evaluate ()
    }
}

// OrNode is similar

EqualsNode : Node
{
    Field field
    Value value

    bool evaluate ()
    {
        return field.value () == value
    }
}

// Likewise for <, >, etc

Answer 2

Questi tipi di query sono spesso presentati come un array ORed di clausole ANDed. Cioè, un formato tabulare in cui si legge in più condizioni ANDed insieme, e poi leggere fino a OR loro. Che porta a qualche ripetizione delle condizioni, ma è facile per gli utenti di leggere, scrivere e capire. Il tuo ((Sex == Male AND Age == 25) OR (Sex == Female AND Status == Single)) AND IQ > 120 campione sarà simile

Sex == Male   & Age == 25        & IQ > 120 
Sex == Female & Status == Single & IQ > 120 

Answer 3

Si potrebbe desiderare di Google per termini come 'calcolo dei predicati' e 'forma normale congiuntiva'.

Answer 4

Devo dire che questo è il motivo per cui i motori di database sono costruiti. Si può fare tutto ciò che si richiede con la logica set e si può anche arrivare al risultato che si sta cercando, ma tesi sono problemi standard risolti da database e SQL. Si può anche guardare a LINQ per una soluzione in codice.

Answer 5

Suona come è necessario creare un'interfaccia utente che permette la creazione di un semplice albero sintattico. Quando le presse GO si può poi a piedi l'albero e creare un albero di espressione LINQ da quella struttura di interfaccia utente. Eseguire la query LINQ e poi elaborare i risultati in base alle esigenze. Vorrei quindi consiglierei di leggere su alberi espressione LINQ.