Verification expression logique

Question

Bonjour à tous,
Dans mon programme, j'ai un champs dans lequel l'utilisateur doit entrer une expression logique du type : "operande"  + "operateur" + "operande"
"operande" pouvant être :
une lettre ou "(NOT lettre)" ou une équation logique commençant par une "(" et finissant par une ")" 

"operateur" peut être : AND, OR, NOR

Au départ j'avais écris une fonction récursive qui controlait une chaine de type "A AND NOT B OR C" mais finalement je dois gérer des chaines de type : "(A AND (NOT B)) OR (C AND D)"
Mais je ne sais pas comment m'y prendre avec les parenthèses pour controler que l'expression entrée est conforme.

Y a t il des algo types pour vérifier que la chaine entrée est bien formée?

Je n'utilise pas de base de données pour mon appli

Merci

florenth · Answer

Salut, Alors, pour ce genre de trucs, je ne suis pas sûr qu'une expression régulière fasse l'affaire. Mais tout dépend de ce que tu cherches à faire:

Soit juste vérifier la syntaxe de l'expression, dans ce cas une procédure récursive simple fait l'affaire

Soit l'évaluer entièrement et donner un résultat, alors dans ce cas il va falloir aller chercher plus loin.

Ressources Delphi, sources, tutoriaux, actu, ...: www.mx-dev.nethttp://te%3C/body

cptpingu · Answer

Le plus simple et le plus élégant reste d'utiliser une grammaire formelle. Une fois ton AST (arbre de syntaxe abstraite) construit, il est facile de calculer et vérifier la validité de l'expression obtenue.

Voici commen j'écrirais une grammaire pour ton problème:

prog ::= expr

expr ::= '(' + expr + ')'
           | value
           | expr op expr
           | 'NOT' expr

op ::= AND
        | OR
        | NOR

value ::= TRUE
            | FALSE
            | une variable

PS: "Regular expression" ne se traduit pas par "Expression régulière" (beurk !) mais par "Expression rationnelle". C'est comme traduire "library" par "librairie" au lieu de "bibliothèque", c'est très moche !

Caribensila · Answer

Ok !
Alors j'ai rien dit...    

PS: Le jour où les anglophones diront "rational expression", on pourra traduire par "expression rationnelle".
Mais, pour le moment,  ils disent "regular expression", qu'un puriste devrait traduire par "expression réglementaire".
Les expressions rationnelles, quant à elles, restent à inventer...

Pour library, je suis tout-à-fait d'accord avec toi, CptPingu.
Quoique ce sont les anglophones qui ont adopté le mot français "librairie" qui, au XIVème siècle voulait dire "bibliothèque" (cf: la librairie du château de Chenonceau).
Mais c'est sûr que peu de programmeurs ont conscience de parler le français de Ronsard en parlant de "librairie".

En tout cas, heureux de te revoir parmi nous et bonne année à toi.  :)))

florenth · Answer

Ouais bon... regular veut dire (entres-autres) régulier donc pour la traduction, il faudra repasser. On pourrait aussi traduire par "familier" qui est le sens de ce mot mais là, ça devient hors-sujet ! Surtout que les regex sont loin d'être familières !

Sinon, AST, ça veut dire "arbre à syntaxe trrrabstraite "... euh pardon ! abstract syntax tree ! Sont gonflants ces anglais ! 

Sinon, pour éviter les arbres syntaxiques si c'est hors de ta portée (comme c'est le cas pour moi), y'a moyen de s'en sortir avec ce lien : http://recursivite.developpez.com/?page=page_3#LII-D
D'ailleurs ce cours est une vraie anthologie sur la récursivité, les concepts étudiés dedans sont vraiment intéressants.

Voila, c'étaient mes 3 cts (3 au lieu de 2... c'est l'inflation).

Ressources Delphi, sources, tutoriaux, actu, ...: www.mx-dev.nethttp://te%3C/body

mike600river31 · Answer

Merci pour vos reponses,
Si je peux eviter les arbres syntaxiques ca m arrangerait.

@florenth : J'ai consulté des cours avec ce type d'exemple, pour le moment j'ai un algo qui ne tient pas compte des parentheses et qui fonctionne, mon gros probleme est d'ajouter la gestion des parentheses dans mon algo

cptpingu · Answer

Si tu ne cherches qu'à vérifier la syntaxe, alors ce langage est suffisament basique pour te passer de la construction d'un arbre. Il te suffit de suivre la grammaire et de lever une erreur si celle ci n'est pas suivie.

Dans un premier temps tu construis une liste de token à partir de ton expression. C'est à dire que tu stockes dans une liste chainées ou une stringlist, les différentes composantes de l'expression. Par exemple pour "(A AND (NOT B)) OR (C AND D)" cela donnerait: (, A, AND, (, NOT, B, ), ), OR, (, C, AND, D, )

Une fois que tu as cette liste de token, tu regardes la grammaire et tu vérifies quand tu te trouves sur un token si le token suivant est attendu. Par exemple apres une parenthèse ouvrante '(' il ne peut y avoir qu'une parenthèse ouvrant, une valeur ou un opérateur. Si tu tombe sur autre chose ton expression est surement invalide. Tu peux en faire de même pour tous les tokens.

Une fois ceci fait, tu devras aussi vérifier que le nombre de parenthèses ouvrantes est la même que celle fermantes.

mike600river31 · Answer

Ca me parait pas mal du tout comme idee de vérification.
Par contre ca m amene a me poser une autre question (surement bete d'ailleurs) :
Comment decouper mon expression de depart?
Lettre par lettre en testant, quand on trouve un A si il est suivi de N et D
(et pour O si il y a un R et pour N si il y a un O et un T)?
ou on peut faire ce decoupage de maniere plus propre?

cptpingu · Answer

Je serais tenter de te conseiller de la faire lettre par lettre. Sachant que tes seuls séparateurs sont " ", "(" et ")". Il suffit de stocker tous token en prenant en compte le fait qu'il soit séparé par ces délimiteurs.
Par exemple pour: "(A        OR B ) AND  C"
ca donnerait lettre à lettre:
(, A, , , , , OR, B, , ), AND, , C

Tu peux procéder comme suit:

index = 0;
list = nouvelle liste.
flux = ton expression.

tant que (index < taille(expression))
  tmp = "";
  si flux[index] == "(" ou == ")" alors
     list.ajouter(flux[index])
  sinon
    tant que (index < taille(expression) et flux[index] != '(' et != ')' et != " ") faire
      tmp = tmp + flux[index] ;
      index = index + 1
    fin tant que
    list.ajouter(flux[index])
  fin si
  si index < taille(expression) et (flux[index] == "(" ou == ")") alors

     list.ajouter(flux[index])
  fin si
  index = index + 1
fin tant que

C'est pas optimisé, fait un peu l'arrache et en langage algorithmique. (pas de compilo sous la main, dsl).

cptpingu · Answer

Une petite erreur s'est glissé, j'avoue ne pas avoir testé. il faut rentrer le 2eme:
"  si index < taille(expression) et (flux[index] == "(" ou == ")") alors
      list.ajouter(flux[index])
  fin si"
dans le "sinon".

Caribensila · Answer

Tu peux aussi faire un préfiltrage à la saisie. Au minimum :

procedure TForm1.FormCreate(Sender: TObject);
  begin
  KeyPreview := true;
end;



procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
  begin
  If not(Key in ['A'..'Z',#8 ,#32,#40,#41]) then Key := #0;//ou 'A'..'z' si minuscules acceptées.
end;

mike600river31 · Answer

Merci beaucoup pour votre aide

@CptPingu : Des que j'ai fini l'operation en cours, j essaie ton algo. 

@Caribensila : J ai la meme fonction sur mon champ de saisie, sauf le nom qui differe un peu. Je trouve que c est donc une excellente idee :)

mike600river31 · Answer

Pour l'algo, ai-je effectué la bonne modif pour l'inbrication du 2e si?
et n'est-ce pas tmp qu il faut ajouter a la liste plutot que flux[index] (en rouge) ?

Sinon pour le code, j'ai utilisé un tableau dynamique plutot qu une liste chainée, simplement parceque j'ai deja travaillé avec et jamais avec les listes chainées.
Pour le moment je ne recupere que (' ',AND,'(',NOT,B )

Pouvez me dire ce qu il faut arranger dans l algo ci dessous, et si vous voulez que je poste mon code.

index = 0;
list = nouvelle liste.
flux = ton expression.

tant que (index < taille(expression))
  tmp = "";
  si flux[index] == "(" ou == ")" alors
     list.ajouter(flux[index])
  sinon
    si index < taille(expression) et (flux[index] == "(" ou == ")") alors

        list.ajouter(flux[index])

    sinon
      tant que (index < taille(expression) et flux[index] != '(' et != ')' et != " ") faire
        tmp = tmp + flux[index] ;
        index = index + 1
      fin tant que    
      // list.ajouter(flux[index])
      list.ajouter(tmp) 
    fin si
  fin si

  index = index + 1
fin tant que

florenth · Answer

Plutot que de trop s'attarder sur du pseudo-code, autant discuter de Delphi, le code est est même bien plus compréhensible.

Avec une fiche, un TEdit, un TMemo et un TButton, on peut faire ça pour tester :

procedure TForm1.Button1Click(Sender: TObject); var R: Integer; begin R : = ParseExpression(Edit1.Text, memo1.Lines); if R <> 0 then memo1.Lines.Add(Format('Caractère illégal à la position %d: %s', [R, Edit1.Text[R]])); end;

Je pense que cels se passe de commentaire, tout est expliqueé dans le code. A noter l'utilisation de TStrings, très simple, et ne pas oublier qu'une chaîne commence à l'index 1 et se termine à l'index Length(S), contrairement aux tableaux. De plus, cette petite fonction permet de faire un premier tri pour savoir si la chaîne entrée contient des caractères illégaux. A+ Flo Ressources Delphi, sources, tutoriaux, actu, ...: www.mx-dev.nethttp://te%3C/body

cptpingu · Answer

@mike600river31: Tu as correctement rentré le morceau de code dans le sinon. Par contre c'est bien list.ajouter(flux[index]) et non pas list.ajouter(tmp). En effet, on ajoute ici le caractère spécial trouvé et non tmp qui n'a rien à voir à ce niveau là.

Toutefois je te conseille de prendre la fonction de florenth qui est très bien (propre et commenté).

florenth · Answer

Tiens, je viens de m'apercevoir qu'en allant un peu plus loin dans le cours que je te donnais en lien, on tombes pil poil sur ce que tu cherches à faire: évaluer une expression arithmétique.
Toi ,comme ce n'est "qu'une expression logique", ce sera encore plus simple, et les principes mis en œuvre dans ce cours sont je le répète carrément trop intéressants ! (je pense à l'arbre bien sûr mais aussi à l'automate à pile)
Ça fait un moment que je connais ce cours, ben je vais le relire tellement c'est bien expliqué.

C'est ici définitivement: http://recursivite.developpez.com/?page=page_8#LVII-C
Comme quoi la marge de manœuvre est grande en programmation... j'en ai les horizons tout ouverts ! 
[Toi aussi Cari hein ? Je suis sûr que tu t'émoustilles devant ces arbres binaires...]

++
Flo

Ressources Delphi, sources, tutoriaux, actu, ...: www.mx-dev.nethttp://te%3C/body

Caribensila · Answer

@florenth
Bein oui.
Surtout que je ne connaissais pas ce cours qui est super clair.
Je sens qu'il va finir imprimé pour me suivre dans mes déplacements (héhéhé).

Merci pour ce lien, Flo. C'est l'événement de la journée pour moi.

PS: Je sens aussi venir des sources qui vont traiter de ce sujet...  Pas vrai?  ;)
Mais n'oublie pas trop la philo quand même (beurk! comme dirait CptPingu).  lol

Verification expression logique

16 réponses

Votre réponse

Discussions similaires