Comment pouvons-nous analyser des expressions booléennes en C à l'aide de Boost.Spirit pour créer une structure arborescente, respectant la priorité des opérateurs ?

Analyse d'expressions booléennes en C

Introduction

Nous visons à créer un analyseur qui transforme une expression booléenne en une structure arborescente, en respectant les règles de priorité des opérateurs (pas, et, xor, ou).

Tokenisation

Pour commencer, nous allons définir des expressions régulières pour faire correspondre différents jetons dans l'expression :

• Variables : Séquences d'un ou plusieurs caractères alphabétiques
• Opérateurs : "et", "ou", "xor", "not"
• Parenthèses : "(" et ")"

using namespace boost::spirit::qi;
typedef std::string var;
qi::rule<std::string::const_iterator, var(), qi::space_type> var_ = qi::lexeme[+alpha];
qi::rule<std::string::const_iterator, std::string(), qi::space_type> operator_ = 
    keywords("and" | "or" | "xor" | "not");
qi::rule<std::string::const_iterator, char(), qi::space_type> parenthesis_ = qi::char_("()[]");

Règles de grammaire

Ensuite, nous définissons des règles de grammaire à combiner tokens :

• Expression : Commence par soit une expression entre parenthèses, une variable ou "pas" suivi d'une expression
• Sous-expression : Suit les règles de priorité (non, et, xor, ou)

qi::rule<std::string::const_iterator, expr(), qi::space_type> expression_ = (
    '(' >> expression_ >> ')'
) | var_ | operator_ >> expression_;

qi::rule<std::string::const_iterator, expr(), qi::space_type> sub_expression_ = 
    expression_ >> *operator_ >> expression_;

Parsing

Pour analyser l'expression, nous utilisons une fonction boost::spirit phrase_parse, qui tente de faire correspondre la chaîne d'entrée entière aux règles de grammaire.

std::string input = "(a and b) xor (c and d)";
auto it = input.begin();
auto end = input.end();
expr parsed_expression;

bool success = phrase_parse(it, end, expression_, qi::space, parsed_expression);

if (success && it == end) {
    std::cout << "Parse successful!" << std::endl;
} else {
    std::cerr << "Parse failed!" << std::endl;
}

Construire l'arbre

Une fois l'expression analysée, nous pouvons construire l'arbre arborescence. Voici un exemple d'implémentation :

typedef std::vector<expr> expr_set;
expr_set nodes;

void create_node(const expr& sub_expr) {
    if (sub_expr.is<std::string>()) {
        nodes.push_back(sub_expr.get<std::string>());
    } else {
        nodes.push_back(expr_set{sub_expr.get<expr_set>()});
    }
}

void build_tree(const expr& root) {
    if (root.is<std::string>()) {
        nodes.push_back(root.get<std::string>());
    } else {
        expr_set sub_expressions = root.get<expr_set>();
        for (const auto& sub_expr : sub_expressions) {
            create_node(sub_expr);
        }
    }
}

Exemple d'utilisation

input = "(a and b) xor (c and d)";
it = input.begin();
end = input.end();

if (phrase_parse(it, end, expression_, qi::space, parsed_expression)) {
    std::cout << "Parse successful!" << std::endl;
    build_tree(parsed_expression);
} else {
    std::cerr << "Parse failed!" << std::endl;
}

for (const auto& node : nodes) {
    std::cout << node << std::endl;
}

Sortie :

(
a
and
b
)
xor
(
c
and
d
)

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!