ÉVALUATEUR D'EXPRESSIONS BOOLÉENNES (BEE)
cptpingu
Messages postés
3837
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
28 mars 2023
-
10 juil. 2011 à 17:08
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 20 juil. 2011 à 14:27
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 20 juil. 2011 à 14:27
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/53361-evaluateur-d-expressions-booleennes-bee
https://codes-sources.commentcamarche.net/source/53361-evaluateur-d-expressions-booleennes-bee
20 juil. 2011 à 14:27
cas ++i:
add i, 1
cmp i, n
jge LABEL
cas i++:
cmp i, n
jge LBEL
add i, 1
Il n'y a fort heureusement pas besoin de recopie ni rien d'autre.
15 juil. 2011 à 15:10
12 juil. 2011 à 15:52
12 juil. 2011 à 11:45
J'aurai juste une remarque : meme si ++i est plus rapide que i++, je suis pratiquement sur que tous les compilateurs modernes un peu serieux sont capables d'optimiser ca tout seul, surtout si il n'y a rien autour (si tu vas par la, pourquoi ne pas declarer la variable en "register" :o) (c'est une blague, ne le faites pas ;o) )).
Et puis je crois que ton "pseudo code equivalent" devrait plutot etre : {itTmp it; it it + 1; return itTmp; }
Pour le xor, effectivement c'est un peu un outil de base.
Si tu veux faire un truc un peu plus marrant a coder, tu peux essayer d'implementer un DEFFN (definition de fonctions utilisateur) et modifier ton code pour charger un fichier d'initialisation au demarrage de ton parseur.
J'avais fait ca lors d'un de mes premier projets scolaires (et eu une bonne note pour l'originalite :o) ).
En gros, on devait coder une calculatrice scientifique avec plein de fonctions sin, cos, tan, etc.
Au lieu de tout coder en C, j'avais uniquement fait sin(x), puis dans mon fichier d'initialisation j'avais des trucs genre :
DEFFN cos(x)=sin(x+pi/2)
DEFFN tan(x)=sin(x)/cos(x)
Enfin, tu vois le genre. Avec ca, tu peux rajouter simplement les XOR, NAND, NOR, etc... a ton parseur.
Eric
10 juil. 2011 à 17:36
Pour le XOR, il est vrai que j'aurais pu le mettre, mais il me semble que ce n'est pas un opérateur "de base" au sens où il peut être construit à partir des trois autres (!, &, |). Mais c'est vrai que ça pourrait simplifier de le mettre.
Pour ce qui est de la gestion des tokens, c'est vrai que c'est pas top.
Pour ce qui est le l'indice de la classe Error, je vois pas trop comment je pourrais retrouver le bon indice, mais je vais chercher.
Sinon, il faudra en effet que je regarde un peu ce que donne la méthode AST, ça peut être intéressant pour aller encore plus loin.
Voilà je vais voir ça et le reste prochainement !
10 juil. 2011 à 17:15
std::cout << std::endl;
std::cout << err.src() << std::endl;
std::cout << std::setw(err.ind() + 1) << "^" << std::endl;
std::cout << std::setw(err.ind() + err.desc().length()) << err.desc() << std::endl;
S'écrit:
std::cout << std::endl
<< err.src() << std::endl
<< std::setw(err.ind() + 1) << "^" << std::endl
<< std::setw(err.ind() + err.desc().length()) << err.desc() << std::endl;
10 juil. 2011 à 17:08
Plusieurs remarques, tout de même:
* À la racine d'un projet, on met généralement un Makefile. Ça évite de rechercher où sont placés les autre Makefile.
* Au niveau des exemples, ils ne sont pas très clairs. Par exemple, l'exemple "simple" est difficilement manipulable. Il aurait été préférable de donner en argument une chaîne de caractère, ou l'entrée standard, et que tu parses l'expression. C'est très inconfortable de jouer avec des options qui ne devraient pas l'être.
* Il manque le xor (^), non ?
* L'exemple "table" est en revanche bien fait, et agréable à utiliser.
* Ton "Error" donne la position dans le chaîne normalisée. Mais la normalisation est un processus interne, un détail d'implémentation qui ne regarde par l'utilisateur de ta classe. Il faudrait donc renvoyer la position dans la vraie chaîne donné en argument.
Au niveau du principe du code:
* Ok, ton code fonctionne, mais tu utilises une technique non optimisé, mal adapté et peu maintenable. La technique usuelle, est d'utiliser un AST. C'est à dire qu'on parse une chaîne et que l'on crééer un arbre à partir de la grammaire du langage désiré. On effectue ensuite les actions sur cet arbre (généralement avec un design pattern Visitor).
* Ce n'est pas la meilleure méthode que d'avoir des "replace" de partout, ou de convertir en expression polonaise avant de réappliquer une action.
* Pour conclure, ta technique est tout à fait correcte, mais peu évolutive (avec un AST, il est plus facile d'ajouter des fonctionnalités, comme afficher l'expression de différentes manières, de simplifier une expression booléenne, ou d'appliquer une action quelconque, vu qu'il n'y a qu'un visiteur à écrire à chaque fois, qui s'interfacera tout seul sur ton arbre).
Au niveau technique, pas mal de petits trucs améliorables:
* Plutôt que de vérifier: obj.size == 0 ou obj.size > 0, il est plus optimisé et compréhensible de vérifier: obj.empty() ou !obj.empty()
* oss << (char)FALSE_VAL et enum: Tu fais un enum, mais il est clair que ce n'est pas ce que tu veux. Tu cherches à avoir un caractère et à te servir de sa valeur. Donc à la place d'un enum, tu devrais avoir:
typedef char TOKEN;
static const char OR_OP = '|';
static const char AND_OP = '&';
etc...
Ce qui t'éviterait des casts dégueux, et exprimerait mieux ce que tu cherches à représenter.
* std::vector<std::string> BEE::vars(), retourner une collection par copie, c'est en général, peu judicieux.
* bool BEE::isToken(std::string t) => const std::string& t
* it++ => ++it. Attention, grosse différence de perf entre ++it et it++ ! ++it modifie directement it, tandis que it++ fais une copie de it, modifie la copie de it, et affecte à it, la copie modifiée de it. Donc: ++it => inc(it) et it++ => {itTmp = it; itTmp = itTmp + 1; it = itTMp; }
* isValidSuccession => pas besoin de else si tu as un return.
* return compute(toRPN()); => Niveau perfs, ça fait mal ! On va compter le nombre de copie:
1) Creation d'un std::queue dans toRPN
2) Renvoi d'un std::queue (copie)
3) Passage d'un std::queue à compute (copie)
4) Dans compute, copie des valeurs de la std::queue dans un std::stack (copie)