Discussion :

[Naruto_kun]

Bonjour,

je vous sollicite pour la mise en place d'un algorithme à écrire en C#.

En fonctione d'une certaines règles qui peut être de ces différents type:
- (1&2)
-(1|2)
-(1&2)|(3&4)
-((1&2)|(3&4))&(5|6)
-....
Mes règles peuvent être de écrites de n'importes quelles manières. Il faut comprendre que le chiffres correspondent à des paramètre à saisir dans un formulaire. En fonction de cette règle de saisie, si tout est ok alors le formulaire est valide.
Il faut que je crée une fonction qui me prend en compte tout ces cas et qui me renvoi true ou false si ma saisie est ok.
Bien evidement en entrée je passe un objet qui contient les éléments du formulaire.

Voici un exemple de ce que j'aimerais:
si j'ai 5 paramètres et que ma règle est la suivante (1&2)|(3&4).
Voici le resultat que j'aimerais pour les cas suivants :
- si aucun saisi alors retourner FALSE
- si 1 est saisi et 2/3/4 pas saisie alors retourner FALSE
- si 1 et 2 saisi et 3/4 pas saisi alors retourner TRUE
- si 1/2/4 pas saisi et 3 saisi alors retourner FALSE
- si 1/2/3/4 saisi alors retourner false

Il faut juste que la règle soit suivi.
Je vous sollicite car je ne sais pas par où commencer.

Merci pour votre aide

[plume13]

Hello, comment comptes-tu paramétrer la règle et sous quelle forme se trouvent les paramètres ?

[Naruto_kun]

Salut,

je compte passer par une fonction qui me renverra un booléen.
Je passerais un objet en paramètre qui contiendra tous les paramètres du formulaire avec bien leur numéro (1,2,3,4,...).
La règle sera stocké dans une table SQL et sera fixe pour chaque formulaire mais elle peut avoir des formes différentes comme énoncés dans mes exemples :
- (1&2)
-(1|2)
-(1&2)|(3&4)
-((1&2)|(3&4))&(5|6)

Du coup, la complexité est de regrouper ceux qui font parti d'un même lot de parenthèse et les tester en fonction du OU |et du ET &.

Je reste à dispo si d'autres questions bien évidemment.

[DonQuiche]

En fait la règle est représentée sous forme de chaîne de caractères ? Si oui il y a deux étapes : d'abord parser la chaîne pour en tirer un arbre syntaxique la représentant (opérateurs binaires ayant deux enfants, etc) et ensuite l'interpréter pour valider les résultats. Pour ma part je construirais un arbre constitué d'objets Expression afin de pouvoir directement compiler ça en une fonction évaluable.

Si une étape te pose problème, il serait bon que tu nous dises laquelle.

[Naruto_kun]

DonQuiche> Oui la règle est représentée sous forme de chaine de caractère.
Je comprend pas tout ce que tu me dis mais en effet je voulais construire une sorte de tableau qui contient chaque sous règle mais je suis pas sur d'etre bon.

Pourrais tu etre plus explicite car je ne comprend pas tout tes termes?

Merci

[DonQuiche]

Il ne faut pas construire un tableau de règles mais un arbre de règles. Si tu prends les expressions trees de C# par exemple (System.Linq.Expressions.Expression) un objet "BinaryExpression" a deux enfants (Left et Right) qui sont eux-mêmes du type Expression. Il peut s'agir d'une constante ou d'une autre opérations binaire.

Ainsi l'expression "5 + 4" est construite de cette façon:
Expression.Add(Expression.Constant(5), Expression.Constant(4))

Une fois que tu as bâti l'arbre il est possible de compiler un délégué correspondant.

[Naruto_kun]

Je ne suis pas expert en développement et en algorithme mais bon.

Pourrais tu me schématiser ce que cela donnera avec l'arbre de règles. Il ne faut pas oublier qu'il faut regrouper els règles en fonction de leur parenthèses d'appartenance.

si j'ai ceci : ( (1&2) | (3&4) ) & (5&6)
je devrais tester que le user n'a saisi que 1&2 ou bien 3&4 avec 5&6.

Mes règles varient en fonction de la contrainte imposé. Je peux avoir n'importe quel règle et mon algo doit pouvoir tout gérer.

Merci de ton aide DonQuiche

[DonQuiche]

Pour cet l'exemple l'arbre ressemble à ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// ( (1&2) | (3&4) ) & (5&6)
Intersection
|-- Intersection
|    |-- 6
|    +-- 5
|
+-- Union
     |-- Intersection
     |    |-- 4
     |    +-- 3
     |    
     +-- Intersection
          |-- 2
          +-- 1

C'est ce qu'on appelle un arbre syntaxique, c'est ce qu'utilisent notamment les parsers/compilateurs. Tu peux construire un tel arbre d'expressions en C# avec un code du genre :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
Expression.Intersect(
   Expression.Intersect(  
      MakeExpressionFor(6),
      MakeExpressionFor(5)),
   Expression.Union(  
      Expression.Intersect(  
         MakeExpressionFor(4),
         MakeExpressionFor(3)),
      Expression.Intersect(  
         MakeExpressionFor(2),
         MakeExpressionFor(1))));

Cela dit tu peux aussi choisir de t'en passer et de plutôt reparser à chaque fois l'expression. On fera alors l'évaluation "au fil de l'eau", c'est à dire en même temps qu'on parse.

[Naruto_kun]

Que me conseilles tu?
En entrée de ma fonction j'aurais ma règle de type string et un objet qui contient toutes les valeurs de chaque paramètre (1,2,3,...).
J'aimerais en fonction des valeurs des paramètres renvoyer un booleen pour dire si la règle est vérifié ou non .

De plus, dans ma règle je n'aurais jamais de + ou de 6. j'aurais juste des & et | pour savoir si il faut saisir les 2 params ou un seul des deux.

Merci pour ton retour DonQuiche. C'est super cool d'avoir ton aide.

[DonQuiche]

Un parsage au fil de l'eau est plus simple mais plus lent. Mais ici les performances ne seront pas un problème (aucune différence visible par l'utillisateur) donc je choisirais plutôt le fil de l'eau. J'avais mentionné l'arbre syntaxique au départ parce que c'est la réponse typique au problème.

Maintenant ce n'est pas très compliqué mais il faut que tu sois bien sûr de tes choix :
* Toutes les sous-expressions sont-elles entre parenthèses ? Peux-tu avoir des choses telles que "1&2&3" ou bien auras-tu toujours "(1&2)&3" ou "1&(2&3)" ? Peux-tu avoir des choses telles que "1&2|3", qui t'obligeraient à mettre en oeuvre une gestion de la précédence pour savoir qui du "&" ou du "|" domine ?

* Tu dis que tu n'auras pas de "6", ce n'est pas une erreur? Quelle est la plage valide pour les indices?

* Tu dis que tu auras des tableaux d'objets. Il devrait s'agir de booléens.

[Naruto_kun]

* Toutes les sous-expressions sont-elles entre parenthèses ? Peux-tu avoir des choses telles que "1&2&3" ou bien auras-tu toujours "(1&2)&3" ou "1&(2&3)" ? Peux-tu avoir des choses telles que "1&2|3", qui t'obligeraient à mettre en œuvre une gestion de la précédence pour savoir qui du "&" ou du "|" domine ?

C'est moi qui écrirais les règles mais je les définirais avec le client.
Du coup, je mettrais des parenthèses partout:
- (1&2)
- (1|2)&(3)
- ((1|2) & (3) & (4))
-etc...
Y aura toujours parenthèse pour indiquer qui prédomine. Jamais de soucis à ce niveau.

* Tu dis que tu n'auras pas de "6", ce n'est pas une erreur? Quelle est la plage valide pour les indices?

Erreur de saisie de ma part je voulais taper pipe |. Désole

* Tu dis que tu auras des tableaux d'objets. Il devrait s'agir de booléens.

non c'est bien un tableau d'objet qui contiendra mes paramètres saisi.
Par exmple 1 correspond à une date de début. Du coup, j'aurais un objet param qui contiendra :
- nom param: date de début
- valeur param : 15/12/2013
- num param : 1
....

ainsi de suite pour les autres paramètres. Comme cela je pourrais tester mes règles sans trop de problème.

[DonQuiche]

Voilà le code grosso modo. Dans sa version actuelle il ne support pas les espaces, tu peux gérer ça au fil de l'eau ou en amont, avant de fournir le texte à cette classe..

Code c# :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Evaluator
{
   IArgument[] Arguments;
   string Text;
   int Index;
 
   Char Current
   {
       get { return Text[Index]; }
   }
 
   public bool ParseExpression()
   { 
        var result = ParseLeftOperand();
 
        if (TryParse('|')) result |= ParseExpression();
        else if (TryParse('&')) result &= ParseExpression(); 
 
        return result ;
   }
 
   bool ParseLeftOperand()
   {
        if (TryParse('(')) 
        { 
             var result = ParseExpression();
             Parse(')');
             return result;
        }
        else
        {
             return ParseArgument();
        }
    }
 
   bool ParseArgument()
   {
        var argumentIndex = ParseInteger();
        var argument = Arguments[argumentIndex]; 
        return argument.Evaluate();
   }
 
   int ParseInteger()
   {
        int start = Index;
        while(Current >= '0' && Current <= '9') Parse();
 
        var argumentText = text.Substring(start, Index - start);
        return Int32.Parse(argumentText);
    }
 
   void Parse()
   {
      if (Index >= Text.Length) throw new ArgumentException();
      ++Index;
   }
 
   void Parse(char c)
   {
      if (Current != c) throw new ArgumentException();
      Parse();
   }
 
   bool TryParse(char c)
   {
      if (Index >= Text.Length || Current != c) return false;
      Parse();
      return true;
   }
}

EDIT : version corrigée.

[Naruto_kun]

Je n'ai pas saisi tout ton code. Il ne permet que de traiter une règle entre parenthèse non?

Pourrait on le parcourir ensemble?
Dans ton cas, enfin je pense que tu parcours toutes la règle pour attribuer un booléen si l'expression est vérifié ou non.

C'est à dire si tu as ceci :
(1&2)|(3&4)|(5&6)
tu vérifies d'abord (1&2) si ok alors tu as (true) ensuite (3&4) si nok tu (False) et tu quittes. Ce qui veut dire pas besoin de vérifier (5&6)
A la fin c'est comme si tu avais ceci : (true)|(false)...

Je me suis peut être mal exprimé et j'en suis désole.

[Naruto_kun]

DonQuiche > Je ne comprend pas tout ton script. Pourrais tout le revoir ensemble ? Il y a certaines lignes de code que je ne comprend pas.

Merci pour ton retour

[DonQuiche]

Bonsoir.

Il y a effectivement un bogue à corriger concernant la gestion des parenthèses.

Cela étant dit, non, on ne cherche pas à optimiser pour renvoyer un résultat le plus tôt possible. Même si l'opérande gauche d'un OU est vraie, on va quand même parser et évaluer l'opérande droite. Il serait bien sûr possible de compliquer l'algo pour optimiser.

[Babyneedle]

Prenons un peu de recul.

Il s'agit ici d'évaluation dynamique d'expression?

Ça tombe bien, il existe FLEE...

Jettez-y un oeil pour voir si ça peut vous convenir.

Pat

[Naruto_kun]

Bonjour,

Babyneedle > Merci pour ta réponse. Je ne pense pas utiliser FLEE. Je compte rester dans le traditionnel .

Donquiche > Pourquoi devrions nous tout parser au lieu de sortir au moment ou l'on est à False. Ce serait plus simple non. De plus, comment traiterais tu un cas avec plusieurs sous parenthèses car il faut vérifier dans un premier la premiere expression dans ton cas pour ensuite ressortir.

Il faudrait que l'on en discute. Je n'ai toujours pas commencé l'écriture de mon algo car je veux bien comprendre le tout.

Merci pour vos réponses. Je continue à fouiner et voir comment faire cela. En tout cas, ton algo m'aide beaucoup

[DonQuiche]

Donquiche > Pourquoi devrions nous tout parser au lieu de sortir au moment ou l'on est à False.

Considère l'expression : (a & b) | c
Tu viens d'évaluer que a est faux? Et alors, c peut être vrai.
Tu viens d'évaluer que a est vrai? Et alors, b peut-être faux.

Le mieux que tu puisses faire c'est, dans certains cas, parser sans évaluer. Tu peux prendre cette décision après avoir parsé l'opérateur. Mais tu es toujours obligé de parser l'opérande droite pour savoir à quel niveau reprend l'expression parente.

Pour reprendre l'exemple précédent, si "a" est faux et que tu as rencontré "&", tu sais déjà que le résultat local sera faux mais tu dois quand même parser b pour savoir à quelle position redonner la main au parent afin qu'il détecte "|".

Si tu veux éviter les évaluations superflues, alors ajoute un paramètre booléen "skipEval" à ParseExpression et ParseArgument. Mais à moins qu'il y ait bel et bien un problème de performances, je te recommande de garder le code le plus simple possible. N'optimise pas ce qui n'a pas besoin de l'être.

De plus, comment traiterais tu un cas avec plusieurs sous parenthèses car il faut vérifier dans un premier la premiere expression dans ton cas pour ensuite ressortir.

J'ai du mal à voir ce que tu veux dire.
Pour les parenthèses la modification à faire est simple : si une expression commence avec une parenthèse, on parse celle-ci, on descend d'un niveau (récursion) et une fois remonté on reparse une parenthèse fermée. Le résultat constitue alors l'opérande gauche.

[Naruto_kun]

Tu as complètement raison, je me suis embrouiller tout seul. (L'algo n'est pas simple)

Je ne vois pas comment faire car si a&b est faux il faut que je continue car j'ai un | (ou) pour vérifier c.
Pour des expressions plus complexes et longues ca ne sera pas simple car je dois pouvoir stocker le résultat de l'expression precédente soit vrai soit faux pour continuer et vérifier dans quel parenthèse je suis.

( ( (1&2)|3 ) | ( (4&5)|(6&7) ) )
Ce sera pas simple de tester cela car il faut regrouper ( (1&2)|3 ) et l'evaluer.
Ensuite regrouper ( (4&5)|(6&7) ) et l'evaluer.
Pour finir vu qu'il y a un |(ou) il faut évaluer les 2 résultats.

Oulalalal quel galère. Je pèche d'un rien

[DonQuiche]

Toutes les décisions peuvent être prises au fil de l'eau en fonction de l'état précédent (résultat déterminé jusqu'ici, valeur canEval, etc) et du caractère courant. Ton algo n'a pas besoin d'avoir conscience du parent ou de l'ensemble de la structure. Imagine-toi simplement en train d'évaluer une expression qu'on te dévoilerait petit à petit, un caractère après l'autre.

( -> début d'une sous-expression
a -> on évalue, renvoie faux
& -> donc on n'aura pas besoin de la suite.
b -> on parse, sans évaluer, on retourne faux par convention (mais on pourrait choisir vrai)
) -> fin de la sous-expression, résultat faux & faux
| -> donc on aura besoin de la suite
c -> on évalue, renvoie vrai, résultat faux | vrai