Discussion :

[oni13]

Bonjour,

je cherche une solution pour valider le format d'une formule de calcul mathématique, par exemple:
2*(1+3/4) est valide
2*1++5 n'est pas valide
2*(4+5 n'est pas valide

La validation doit s'effectuer avec des opérateurs basiques uniquement (+ - / *)

Existe-t-il des solutions pour vérifier cela?
Une expression régulière? un algorithme?
Autrement : une librairie java ou javascript

Je ne trouve aucune solution existante sur ce sujet, et il a l'air complexe de mettre en place une telle vérification

Auriez vous une piste?

merci

[wiwaxia]

Bonjour,

... Auriez vous une piste? ...

# Mettre la formule sous forme de chaîne de caractères, après élimination des éventuels espaces (' '):

# Repérer tous les doublets interdits de caractères consécutifs ('+*', '+/', '*/', ...etc);

# Compter algébriquement les parenthèses en parcourant la formule, et en codant
Np:= Np + 1 pour toute parenthèse ouvrante '(',
Np:= Np - 1 pour toute parenthèse fermante ')';
le bilan doit être nul: Np_final = Np_initial = 0 .

Cela ne doit pas poser de difficulté dans le cas d'une formule numérique; dans le cas d'une formule algébrique, il faut voir quels sont les symboles autorisés.
Le signe "moins" peut aussi poser problème, dans la mesure où il peut intervenir en tant qu'opérateur unaire de changement de signe; la paire '+-' sera acceptable ou non, suivant les règles de syntaxe du logiciel traitant la formule.

[lulzec]

Un automate fini te fait ça. En gros lexer parser. Lex/yacc, ou antlr4 par exemple.
Antlr4 fonctionne très bien avec java. Il te parse tout ça, et te retourne un arbre du parsing effectué, ou une erreur.

Par exemple avec antlr4, un fichier comme ça fait l'affaire:

Code :

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
grammar Arit;
 
parse: e EOF ;
 
e returns [int er]: 
      '-' e 
    | '(' e ')' 
    | e '/' e 
    | e '*' e 
    | e '-' e 
    | e '+' e 
    | INT
;
 
 
WS : [ \t\r\n]+ -> skip ; // skip spaces, tabs, newlines
INT: '0'..'9'+;
NEWLINE: [\n]+;

Tu peux compiler ça avec un truc du style java -jar antlr4.jar fichier.g4 après avoir télécharger antlr4 et tout ça. Ca te créer un code java qui parse tout ça. Tu peux tester en lançant le parser sur une entrée s'il y a une erreur au cours du parsage par exemple

[oni13]

Ok, merci pour ces réponses.

Je vais m’intéresser à ce fameux antlr4.

Développer un algo maison de validation me semble complexe, car sur cette idée, il faut penser à répertorier tous les cas "mauvais", ce qui ne semble pas être un mince affaire.
Il me semble également peu efficace de coder quelque chose de complexe (enfin, de mon point de vue) si il existe déjà des solutions fiables.

Merci

[lulzec]

Après apprendre antlr c'est pas trivial non plus !
Mais c'est utile pour faire ça

[dourouc05]

Un peu en vrac…
D'un point de vue théorique, impossible de résoudre ce problème avec une machine d'état finie : il faut compter les parenthèses, ce qui est impossible (même chose pour des expressions régulières). Il faut absolument généraliser https://fr.wikipedia.org/wiki/Automate_%C3%A0_pile (ANTLR étant un bazooka pour tuer une mouche, ici ).
Pour un algo maison, ce n'est a priori pas trop compliqué, ça se résume à une pile (https://en.wikipedia.org/wiki/Shunting-yard_algorithm). Dès que l'expression à analyser n'a plus de sens, alors il y a un problème.