Comment analyser efficacement des expressions booléennes avec Boost Spirit ?

Analyse d'expressions booléennes à l'aide de Boost Spirit

Problème :

Comment analyser efficacement les expressions booléennes (en utilisant C ) qui respectent les règles de priorité, y compris les opérations telles que AND, OR, XOR et NOT. Le but est de construire une représentation arborescente de l'expression qui préserve l'ordre de priorité.

Solution :

1. Type de données abstrait (ADT) de l'arbre d'expression :

Pour représenter l'arbre d'expression, un ADT est défini à l'aide de la prise en charge des variantes récursives de boost::variant :

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<binop<op_and> >,
        boost::recursive_wrapper<binop<op_xor> >,
        boost::recursive_wrapper<binop<op_or> >
        > expr;

Où chaque type dans la variante représente un nœud dans l'arbre d'expression :

• var : Nœud feuille représentant un variable
• unop : nœud d'opérateur unaire (par exemple, NOT)
• binop : nœud d'opérateur binaire (par exemple, AND, XOR, OR)

2 . Règles de grammaire :

Une grammaire sans contexte est définie pour spécifier les règles de syntaxe des expressions booléennes :

struct parser : qi::grammar<It, expr(), Skipper>
{
    parser() : parser::base_type(expr_)
    {
        using namespace qi;
        expr_  = or_.alias();
        ...
    }
};

3. Analyser et construire l'arbre :

À l'aide de Boost Spirit, un analyseur est généré en fonction des règles de grammaire. L'analyseur consomme l'expression d'entrée et construit l'arbre d'expression correspondant.

expr result;
bool ok = qi::phrase_parse(f, l, p > ';', qi::space, result);

4. Impression de l'arborescence d'expression :

Un visiteur d'impression d'arborescence est implémenté pour afficher l'arborescence d'expression de manière conviviale :

struct tree_print : boost::static_visitor<void>
{
    void operator()(const binop<op_and>&amp; b) const { print("and ", b.oper1, b.oper2); }
    ...
};

Exemple d'utilisation :

std::cout << "result: " << result << "\n";

Sortie :

result: ((a and b) xor ((c and d) or (a and b)))

Cette approche fournit un cadre robuste et extensible pour analyser les expressions booléennes et créer une représentation structurée pour un traitement ou une évaluation ultérieurs.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!