Discussion :

[Invité]

Bonjour,

Je cherche dans le cadre de mon projet à simplifier des expressions booléennes ... mais il me faut un analyseur syntaxique préfait (car c'est niveau maîtrise et je ne suis qu'en 2éme Année de DUT Informatique) mais je n'ai pas trouvé mon bonheur sur la toile ... quelqu'un pourrait il m'éclairer?

Merci.

[Razgriz]

Si tu as une expression booléenne à plusieurs variables, du type A&&(B||D) ||A&&C et que tu veux en calculer la valeur je peux t'aider, y faut faire un parser, je veux bien t'expliquer mais c'est un peu long.

Mais si tu as une telle expression et que tu veux la simplifier je n'ai acune idée de comment on pourrait s'y prendre. Désolé.

[Invité]

Si tu as une expression booléenne à plusieurs variables, du type A&&(B||D) ||A&&C et que tu veux en calculer la valeur je peux t'aider, y faut faire un parser, je veux bien t'expliquer mais c'est un peu long.

Mais si tu as une telle expression et que tu veux la simplifier je n'ai acune idée de comment on pourrait s'y prendre. Désolé.

oui je veux bien que tu m'explique , le mieux c'est que je te donne mon adresse MSN: sbz29@hotmail.com , pour la simplification j'utilise la méthode du consensus mais ça je verrais plus tard.

merci.

[Razgriz]

Tout d'abord, cf électronique, considère que les && sont des * et les || sont des +, ça simplifieras les explications.
Si t'es pas convaincu voilà pourquoi on peut faire ça :
A * B = B * A A + B = B + A => Commutativité
A * (B + C) = A*B + B*C A + (B * C) = (A+B) * (A+C) => Distributivité
1 * A = A 0 + A = A => Neutre
A * !A = 0 A + !A = 1 => Inverses

Par ailleurs on a aussi :
0 * A = 0 1 + A = 1
A * A = A A + A = A
A*(B*C) = (A*B)*C A+(B+C) = (A+B)+C

Maintenant que tu es convaincu lol , passons à la décomposition :
Ton String de base, est une Expression. Toutes les Expressions sont une somme de Termes (séparés par des +), tous les Termes sont un produit de Facteurs (séparés par des *) et tous les Facteurs sont des doubles (ici les valeurs 1 ou 0), soit des variables, soit des Expressions entre paranthèses. Tu dois donc implémenter une récursion mutuelle, càd que getValue(Expression) va appeler dans son code getValue(Term) qui va appeler getValue(Factor) qui va appeller getValue(Expression), etc...
La récursion s'arrête bel et bien, les cas de base étant les variables ou les doubles.

Astuce d'implémentation : Dans lesdites méthodes, compte les parenthèses et vérifie quue l'expression est profil-équilibrée, i.e. que le nombre de parenthèses ouvertes est égal au nombre de parenthèses fermées, et que si tu considère une parenthèse ouverte comme +1 et une fermée comme -1, que tu ne passe jamais dans le négatif dans le parcours.

L'algorithme présenté ne fonctionne que pour des expressions valides (Tester dans le constructeur de Expression), et ne focntionneras pas si y a des erreurs, style deux + l'un à côté de l'autre ou des conneries comme ça.

J'ai un parseur pour les expressions arithmétiques, je le postérai dès que j'aurais implémenté l'intégration pour les fonctions comme sin, cos, exp, ...

Si tu as besoin d'explications hésite pas.
Voilà un livre très interressant qu parle entre autres de ça et de plein d'autres trucs super utile en algorithmique :
Titre : Concepts fondamentaux de l'informatique
Auteurs : Alfred Aho et Joffrey Hullman
Maison d'Edition : Dunod
ISBN : 2 10 003127 9

Je l'ai chez moi c'est un livre en frnçais très bien expliqué.

[schniouf]

Salut,
J'ai moi aussi fait un IUT informatique (à Belfort) et un de mes projets de 2è année était de réaliser... un analyseur syntaxique des expressions booléennes ! Le programme vérifie que l'expression est correcte, mais c'est pas tout : il la réduit également sous forme de clauses, et tout et tout et tout ! Il te dit aussi s'il s'agit d'une tautologie ou d'une antinomie...

-EDIT-
J'avais posté un lien vers les sources, mais je l'ai retiré...
Normalement on doit pas filer des projets déjà tout fait, c'est pas intéressant du tout pour toi, tu vas rien apprendre, même si tu comprend ce que j'ai fait. On apprend beaucoup plus en faisant soit même. Je pense que tout le monde au début cherche à pomper les projets, et puis avec le temps on se rend compte qu'on n'a pas progressé d'un poil. Alors je préfère ne pas te donner les sources, mais plutôt le principe :

Pour la grammaire, toujours commencer par l'opérateur de plus faible priorité. Ici, il s'agit de l'équivalence (<->) et de l'implication (->). Une fois que tu as détecté un de ces opérateurs, tu analyse récursivement les opérandes de gauche et de droite, qui sont forcément soit une conjonction (&), une disjonction (|), une négation(!), ou bien une expression entre parenthèses (et donc potentiellement une équivalence ou une implication).
Voici l'ordre dans lequel tu dois analyser ton expression :
(1) - Si l'expression n'est composée que d'un terme, c'est une variable. Si ce n'est pas le cas, cherche une équivalence ou une implication.
(2) - S'il y en a une, Pour chaque opérande, applique (1)
(3) - S'il n'y en a pas, cherche une conjonction ou une disjonction
(4) - S'il n'y en a pas, cherche des parenthèses et une éventulle négation

Je t'ai déjà pas mal aidé... à toi de te débrouiller maintenant !

[schniouf]

J'ai un parseur pour les expressions arithmétiques, je le postérai dès que j'aurais implémenté l'intégration pour les fonctions comme sin, cos, exp, ...

J'en ai fait un aussi pour un projet à l'école (celui sur les expression booléennes, remanié à la sauce arithmétique) mais j'ai un peu galéré pour intégrer les fonctions... et en + je manquais de temps.
Par contre, à la demande du prof, les variables sont gérées et sont stockées dans un arbre binaire de recherche suivant leur nom. Là où je suis content c'est que l'arbre est équilibré automatiquement si une de ses branches est trop grande ! Galère comme algorithme
Mais maintenant que j'ai un peu plus de temps, je vais essayer d'ajouter le support des fonctions par système de plugin.

[Razgriz]

Mon parseur n'appele pas un arbre binaire dans le sens ou chaque noeud a un ou plusieurs fils, et pas nécessairement deux. Par exemple si au départ mon expression est composée de trois termes, j'aurais la racine avec comme opérateur le + et comme fils les trois termes. Pour rester général pour les opérateurs implémente-les sous forme d'interface Operator pr exemple, avec une méthode apply.
Un truc du style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
public interface Operator
{
      public static double apply(double ... args);
}

Et pour la classe Plus :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
public class Plus implements Operator
{
     public static double apply(double ... args)
     {
         double sum = 0;
         for(double nbr : args)
              sum += nbr;
         return sum;
     }
}

[schniouf]

public interface Operator
{
public static double apply(double ... args);
}

Ah oui pas bête, même super malin ! Mais nous il nous était demandé d'utiliser les arbres binaires, pour faire des opérations dessus : recherche, rotations, etc. N'empêche que grâce à ça l'équilibrage d'un arbre n'a plus de secret pour moi
En tout cas, ta méthode est super .

[Razgriz]

De rien ;-)

Mais cette méthode avec les Operator et les noeuds est un peu lourde pour la mémoire, je la conseillerais plutôt pour une structure de donnée de type arbre, par pour un appel récursif. Y a moyen de se passer des noeuds et de trouver la valeur sans ça, en décomposant en termes, facteurs,...