Ecco una frase logica:
term1 AND (term2 OR term3) OR term4
Che cos'è un modo efficace di archiviare queste informazioni in una struttura dati?
Ad esempio, dovrei usare un grafico, con una proprietà su ciascun lato che definisce l'operatore per il termine successivo? (Questo suggerimento non ha senso IMO, ma è una struttura dati che potrebbe essere utile per questo)
Ho usato un grafico oggetto per codificare qualcosa di simile prima. Ogni oggetto nel grafico ha la sua struttura.
Ad esempio:
BinaryLogicalExpression : BooleanExpression
{
Left : BooleanExpression
Right : BooleanExpression
Operator : BinaryLogicalOperator
}
ArithmeticExpression : Expression
{
Left : Expression
Right : Expression
Operator : ArithmeticOperator
}
// for modelling brackets...
LogicalGroupExpression : BooleanExpression
{
GroupedExpression : BooleanExpression
}
// to hold constant values...
IntegerConstant : Expression
{
Value : int
}
StringConstant : Expression
{
Value : string
}
Quindi utilizzerei una serie di implementazioni Visitor per attraversare il grafico degli oggetti per la valutazione e l'elaborazione dell'espressione.
Expression
{
Accept(ExpressionVisitor visitor);
}
ExpressionVisitor
{
Visit(BinaryLogicalExpression e);
Visit(ArithmeticExpression e);
Visit(StringConstant e);
Visit(IntegerConstant e);
etc...
}
L'utilizzo di un grafico a oggetti e Visitor semplifica la serializzazione di tali espressioni in XML o in strutture gerarchiche di dati simili.
potrebbe essere usato un array, quindi:
term1 AND ( (term2 OR term3) OR term4 )
sarebbe:
[ {term1},
{ 'OR' : [ { 'OR' : [ {term2} , {term3} ] },
{term4}
]
}
]
in PHP:
array('term1',array('OR'=>array(array('OR'=>array('term2','term3')),'term4')));
questa notazione è usata nel framework CakePhp =).
Good Luck
Vorrei provare gli alberi, nidificarli in modo che ogni livello avesse l'operatore su un ramo sinistro e tutti i dati su un ramo destro ala Lisp.
In C potresti fare qualcosa del genere:
enum NodeType {OPERATOR, VARIABLE};
enum Operator {AND, OR, NOT, IFF, PLY};
struct Node {
enum NodeType typ;
enum Operator op;
struct node *left;
struct node *right;
};
Le parentesi non appaiono esplicitamente nella struttura. Qualsiasi istanza di struct Node con typ == OPERATOR parentesi in modo efficace i due termini a cui fanno riferimento gli elementi left e right . Dovresti anche decidere una convenzione per l'operatore NOT: solo uno di left , right punta al termine negato.
Leggi altre domande sui tag python data-structures logic-programming