begin process at 2012 05 27 16:07:48
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > ÉVALUATEUR D'EXPRESSIONS BOOLÉENNES (BEE)

ÉVALUATEUR D'EXPRESSIONS BOOLÉENNES (BEE)


 Information sur la source

Note :
7 / 10 - par 1 personne
7,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Classé sous :evaluateur, expression, booléenne, bool, BEE Niveau :Initié Date de création :07/07/2011 Date de mise à jour :10/07/2011 18:08:17 Vu / téléchargé :2 663 / 57
Auteur : macsou01

Ecrire un message privé
Site perso
Commentaire sur cette source (7)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
BEE(Boolean Expression Evaluator) permet d'évaluer des expressions booléennes.



Les opérateurs et symboles prédéfinis sont :
0 : faux
1 : vrai
& : opérateur et
| : opérateur ou
! : opérateur non
( : parenthèse gauche
) : parenthèse droite
Il est cependant possible de spécifier ses propres valeurs.

Des variables peuvent de plus être utilisées dans les expressions.

Les erreurs (de syntaxe, de parenthésage, de variable indéfinie) sont gérées et peuvent être récupérées en utilisant un bloc try catch autour de l'appel de la méthode eval (voir l'exemple "simple").
Il est possible de connaître la description de l'erreur et la position du caractère fautif dans l'expression normalisée.

Le code est commenté et documenté (la documentation est déjà générée et le fichier Doxyfile est fourni).

Deux exemples sont fournis avec le code :
- simple : permet d'évaluer des expressions booléenne avec variables et possibilité de choisir ses opérateurs.
- table : permet de générer la table de vérité d'une expression booléenne. (c'est celui qui est affiché ci-dessous)



Attention, le zip et le code fournis sur cette page ne sont pas forcément à jour ! Pour voir les dernières sources, rendez-vous ici : https://bitbucket.org/mcc/dev/src/tip/BEE/

Source

  • #include "../../src/BEE.hpp"
  • #include <iomanip>
  • #include <cmath>
  • int main(int argc, char** argv) {
  • if(argc == 1) {
  • std::cerr << "Usage : " << argv[0] << " expression booleenne"
  • << std::endl;
  • return 1;
  • }
  • try {
  • BEE bee(argv[1]);
  • std::vector<std::string> vars = bee.vars();
  • //Affichage de l'entête.
  • for(unsigned int i = 0; i < vars.size(); i++) {
  • std::cout << vars[i] << " ";
  • }
  • std::cout << argv[1] << std::endl;
  • //On doit trouver toutes les valeurs possibles pour toutes les
  • //variables. Ca revient à convertir en binaire les nombres de 0 à
  • //2 ^ nbVars. On prend ensuite chaque bit de ces nombres et on assigne
  • //chacun d'eux à la variable associée.
  • int nbVars = vars.size();
  • int sizeType = 4 * sizeof(int);
  • int nbLines = pow(2, nbVars);
  • int maxType = pow(2, sizeType - 1);
  • for(int l = 0; l < nbLines; l++) {
  • //On se décale jusqu'aux bits utiles.
  • int t = l << (sizeType - nbVars);
  • //On affiche les bits.
  • for(int i = 0; i < nbVars; i++) {
  • bool valBit = t & maxType;
  • bee.setVar(vars[i], valBit);
  • t <<= 1;
  • std::cout << valBit << std::setw(vars[i].length() + 1);
  • }
  • //On évalue l'expression avec les nouvelles valeurs.
  • bool res = bee.eval();
  • std::cout << res << std::endl;
  • }
  • } catch(BEE::Error err) {
  • 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;
  • }
  • return 0;
  • }
#include "../../src/BEE.hpp"
#include <iomanip>
#include <cmath>

int main(int argc, char** argv) {
	
	if(argc == 1) {
		std::cerr << "Usage : " << argv[0] << " expression booleenne"
				  << std::endl;
		return 1;
	}
	
	try {
		BEE bee(argv[1]);
		std::vector<std::string> vars = bee.vars();
		
		//Affichage de l'entête.
		for(unsigned int i = 0; i < vars.size(); i++) {
			std::cout << vars[i] << " ";
		}
		std::cout << argv[1] << std::endl;
		
		//On doit trouver toutes les valeurs possibles pour toutes les
		//variables. Ca revient à convertir en binaire les nombres de 0 à 
		//2 ^ nbVars. On prend ensuite chaque bit de ces nombres et on assigne
		//chacun d'eux à la variable associée.
		int nbVars = vars.size();
		int sizeType = 4 * sizeof(int);
		int nbLines = pow(2, nbVars);
		int maxType = pow(2, sizeType - 1);
			
		for(int l = 0; l < nbLines; l++) {
			//On se décale jusqu'aux bits utiles.
			int t = l << (sizeType - nbVars);
			
			//On affiche les bits.
			for(int i = 0; i < nbVars; i++) {
				bool valBit = t & maxType;
				bee.setVar(vars[i], valBit);
				t <<= 1;
				std::cout << valBit << std::setw(vars[i].length() + 1);
			}
			
			//On évalue l'expression avec les nouvelles valeurs.
			bool res = bee.eval();
			std::cout << res << std::endl;
		}
	} catch(BEE::Error err) {
		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;
	}
	
	return 0;
}

 Conclusion

Cette source peut être utile notamment pour savoir comment convertir une expression (booléenne ou non) en notation polonaise inversée. (l'algorithme n'est pas entièrement de moi, sa structure provient d'une page Wikipédia mentionnée au dessus de la fonction concernée).

Il existe peut-être des bugs, si c'est le cas, merci de me les indiquer.

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

07 juillet 2011 22:16:03 :
Correction d'une faute d'orthographe dans le titre.
09 juillet 2011 15:30:09 :
Ajout d'un exemple (table) et quelques modification dans le code de l'évaluateur.
10 juillet 2011 18:08:20 :
Quelques modifications selon des conseils prodigués dans les commentaires (mais il reste des choses à faire !).

 Sources du même auteur

Source avec Zip Source avec une capture COURBE DE BÉZIER
Source avec Zip Source avec une capture SYSTÈME D'ANNULER-REFAIRE PAR ARBRE (TURS)
Toutes les sources de macsou01

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec Zip EVALUATEUR D'EXPRESSION ARITHMÉTIQUE par matrx180vTitanium
Source avec Zip Source avec une capture EVALUATEUR_EXPRESSION_ARITHMETIQUE par Donald180v
Source avec Zip Source avec une capture ANALYSEUR_LEXICAL_TABLEAU par Donald180v
Source avec Zip Source avec une capture ANALYSEUR LEXICAL par Donald180v
EVALUATEUR D 'EXPRESSION!! par van007

Commentaires et avis

Commentaire de CptPingu le 10/07/2011 17:08:45 administrateur CS

Le code est propre, il y a du doxygen utilisé judicieusement, c'est plutôt agréable. Il y a plus de bons points que de mauvais, mais seule la critique des mauvais t'aidera à progresser. Donc je vais te faire une critique détaillée, mais il ne faut pas en déduire que ce que tu as fait est mauvais. Bien au contraire.

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)

Commentaire de CptPingu le 10/07/2011 17:15:49 administrateur CS

J'oubliais, ceci:
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;

Commentaire de macsou01 le 10/07/2011 17:36:43

Encore merci pour ces conseils :).
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 !

Commentaire de LeFauve42 le 12/07/2011 11:45:45 7/10

Tres bons conseils CptPingu !
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

Commentaire de macsou01 le 12/07/2011 15:52:24

Ah oui, je vois, LeFauve42, merci pour l'astuce !

Commentaire de CptPingu le 15/07/2011 15:10:34 administrateur CS

@LeFauve42: Je suis d'accord avec toi, tout compilo moderne fera cette optimisation. Mais attention, je parlais de la différence dans le cas ou it est un "iterator", la classe iterator de la STL ! Et là, les types ont été redéfinis, et on a une réelle différence de performance.

Commentaire de BruNews le 20/07/2011 14:27:04 administrateur CS

if(++i < n) ou if(i++ < n) strictement identique en perf pout tout compilo normalement constitué.

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.

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

XML en C++ [ par The_Legacy ] Bonjour tout le monde,Je fais appel à votre aide car je suis dans un cas désespéré. Je ne suis pas un pro du C++, disons que je m'en sors, mais je doi CopyFile en C !!! [ par Zillah ] J'ai trouvé aussi des référence à cette fonction, mais comment l'appliqué ??? Je suis vraiment intrigué. J'avais besoin au départ de seulement un moye sérialisation d'un bool ou un type enum [ par iznogoud ] Bonjour,J'ai un petit problème lorsque j'utilise ma fonction serialize. Je suis incapble de rentrer des types bool ou des types que j'ai créer. Je sai Expression régulières en C [ par CoreBreaker ] Bonjour !Quelqu'un aurrait-il un source pour traiter les expressions régulières de type UNIX en C (reconnaissance + remplacement de motif avec les par Combien pèse un objet de type bool? [ par MoDDiB ] Combien pèse un objet de type bool car mon liver omet de le dire :( ? selon moi 1 bit mais bon on ne sait jamais ^^Merci pour la réponse (oui je sais Thread [ par milhandril ] g un petit pb avec les Trheads. Ca compile bien mais lorsque la fonction associé au Thread se lance une erreur survient. en global g:static bool rech= DLL sous C++ builder 6 [ par ivdz ] Bonjour,Voici une partie du .h de mon exécutable que je dois transformer en DLL (sous C++ builder 6) :#ifndef MODBUSTCPIP_H#define MODBUSTCPIP_Hclass JOYSTICK ? probleme lecture [ par pirate75000 ] Ma fonction est dans une dll!Pourquoiq quand je passe a l'etat 1 le bouton1 et le bouton2je recupere comme info qu'ils sont a zeroDesque je mets deux boucle avec for,petite question! [ par chris5874 ] bonjour à tous,j'aimerai savoir si dans une boucle for(initialisation;condition;expression),bref,une boucle normale,j'aimerai savoir si la condition e analyseur d'expression [ par loicus ] Voila, je cherche une fonction, qui pourrait transformer une expression (suite de char) en une ligne de code qui sera utiliser par le programmeex : ma


Nos sponsors


Sondage...

Comparez les prix


Sony Ericsson XPERIA X10 (1 Go)
Entre 649€ et 649€

Visiter le guide achat

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

A découvrir
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,593 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)