Verification expression logique

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

Salut,

Le plus élégant et le plus didactique pour toi serait d'utiliser les expressions régulières.

Un exemple d'utilisation de la librairie RegExp et, en prime, un excellent  utilitaire pour tester les regexp de l'ami Florenth ici.

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.net [ Lien ]

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 !

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.  :)))

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 : [ Lien ]
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.net [ Lien ]

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

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.

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?

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).