Un parser de fonctions mathématiques

Dans cette page, on va parler de la saisie des fonctions mathématiques et de leur interprétation dans un programme scientifique. Lorsqu'on désire, dans un programme, donner la possibilité à l'utilisateur d'entrer sa propre fonction sous forme d'une chaine de caractères. C'est par exemple le cas pour un programme de résolution d'équations (Ex.: "Entrez l'équation à résoudre...") ou bien d'un traceur de fonctions (Ex.: "Entrez l'équation de la courbe à traçer f(x)=..."). Une fois la chaine saisie, une routine interpréte cette chaine et évalue la fonction qu'elle représente. Une telle routine est appelée couramment un parser d'expressions mathématiques.

Dans le cadre du projet Opale, projet sous licence LGPL, nous avons developpé un parser en langage Java. Dans un premier temps ce parser va servir dans le projet aux tracés de fonctions et à la résolution d'équations différentielles, puis ensuite partout où une expression mathématique devra être évaluée.

L'applet ci-dessous permet de tester une partie des fonctionnalités de ce parser. Il en est à sa toute première version donc n'hésitez pas à rapporter les bugs ici.

Pour utiliser cette applet, vous entrez une expression mathématique dans la première ligne, pouvant contenir les variables x, y, z, t ; dans les lignes suivantes vous entrez les valeurs de ces variables (0 par défaut) et en cliquant sur le bouton le résultat s'affiche sur la dernière ligne.

Dans la suite de cette page nous allons parler brièvement du principe à utiliser pour concevoir un parser ; ensuite un petit retour sur le parser Opale s'impose avec une description de ses fonctionnalités ainsi que de son évolution. On traitera également de son utilisation dans vos programmes Java.

Résumé du principe de conception d'un parser

Dans cette section, nous allons très brièvement présenter une méthode pour programmer un parser sans aucun détail. Le but de notre problème est d'évaluer une expression mathématique contenant les opérations usuelles (+,-,*,/), des nombres, des variables (x,y...), des constantes (Pi...) et des fonctions (cos, sin, exp...). Appuyons-nous sur l'exemple "cos(Pi)+2-5*x".

La première étape de l'algorithme consiste à construire à partir de cette chaine de caractères un arbre ; dans un second temps, le parcours de cet arbre à partir de sa racine, permettra d'obtenir la valeur de l'expression. D'un point de vue algorithmique, le plus délicat est la construction de cet arbre. Une fois obtenu, l'arbre doit être stocké dans une structure de données adaptée et il peut être évalué autant de fois qu'on le souhaite (pour plusieurs valeurs de x par exemple) sans avoir à le recalculer avant chaque évaluation.

L'arbre correspondant à notre exemple est :

L'évaluation de l'expression se fait comme nous l'avons dit en parcourant l'arbre à partir de sa racine. Pratiquement cela peut se mettre en oeuvre aisément à l'aide d'un algorithme récursif.

Fonctionnalités du parser Opale

Le parser fournit dans Opale n'en est qu'à sa première version. L'applet de cette page permet de tester rapidement sa validité sur des expressions pouvant comporter des variables x,y,z ou t. Néanmoins toutes les possibilités offertes par ce parser ne sont pas accessibles dans cette applet. Nous énumérons ainsi, en vrac, les fonctionnalités de cette première version :

• Opérations : +,-,*,/,(,),^
• Fonctions : cos, sin, tan, acos, asin, atan, sqrt, log, log10, exp, abs, rnd, rad, deg
• Constantes : Pi, e (constante d'Euler)
• Prise en compte de variables quelconques (x, y, x1, t, y23, a etc...)
• Les variables peuvent également contenir des expressions mathématiques (ex.: calculer cos(x) avec x=2*Pi ; essayer cela dans l'applet)
• Ajout de fonctions utilisateurs à une variable (ex.:f(x) = 2*sin(Pi+x))
• Pas de distinction majuscules/minuscules

• Gestion de la notation scientifique (ex.: 2e3)
• Elargir la liste des constantes mathématiques et physiques
• Prise en compte de fonctions à deux variables
• Ajouter les fonctions max(x,y), min(x,y), mod(x,y)
• Améliorer le diagnostique des erreurs d'entrée de la chaine
• Interprétation des tests et valeurs booléennes (ex.: 4 > 3 )

Utilisation du parser Opale

Etant donnée que le parser du projet Opale peut être utile dans tout autre contexte, nous donnons la possibilité de le télécharger tout seul afin de pouvoir l'utiliser dans vos programmes. Vous pouvez récupérer ici l'archive oparser.jar qui contient les classes nécessaires pour utiliser le parser dans vos programmes. Ce travail est sous licence LGPL et nous vous invitons à prendre connaissance de cette licence avant utilisation du programme.

Parlons un peu de l'utilisation de ces classes dans vos programmes. Les classes importantes sont au nombre de quatre et figurent dans le package oparser. Il convient donc de placer l'instruction 'import oparser.*;' dans vos programmes ainsi que de fixer la variable d'environnement CLASSPATH convenablement : plus précisemment elle doit contenir le chemin complet vers oparser.jar ou bien il vous faudra compiler en précisant le classpath à chaque fois :

javac -classpath votre_repertoire/oparser.jar LeProg.java

Il est possible de consulter la documentation de ces classes en ligne en cliquant ici (doc en anglais et pas encore complete)

La classe de base est Parser. Commençons donc par un simple exemple qui évalue une expression dans un programme :

import oparser.*;

public class Test1
{
  public static void main(String[] arg)
  {
    Parser parser = new Parser("4-2*sin(x-Pi)*2");
    parser.addVar("x");
    parser.parseString();
    
    parser.setVar("x",1);
    System.out.println(parser.eval());
	
    parser.setVar("x","Pi");
    System.out.println(parser.eval());	
  }
}

Pour tout problème de compilation ou d'execution, n' hésitez pas à écrire : ici.

L'exemple est assez parlant : On instancie un objet de type Parser en précisant la chaine à traduire. Ensuite on déclare les variables utilisées, ici "x", avec la méthode addVar(String). On appelle alors la méthode parseString() pour construire l'arbre. Maintenant que l'arbre est construit on peut fixer les valeurs des variables avec setVar(String,double) ou setVar(String, String), et évaluer l'expression autant de fois que désiré avec la méthode eval().

Voici un autre exemple avec 2 variables x,y. On évalue dans cet exemple l'expression sqrt(x*x+y*y) pour plusieurs valeurs de ces variables dans une boucle.

import oparser.*;

public class Test2
{
  public static void main(String[] arg)
  {
    Parser parser = new Parser("sqrt(x^2+y^2)");
    parser.addVar("x");
    parser.addVar("y");
    parser.parseString();
    for (int i=0;i<5;i++)
      for (int j=0;j<5;j++)
      {
        parser.setVar("x",i);
	parser.setVar("y",j);
	System.out.println("sqrt("+i+"*"+i+"+"+j+"*"+j+") = "+parser.eval());
      } 
  }
}

On note que l'on construit l'arbre par la méthode parseString() qu'une seule fois avant toute évaluation.

Terminons par un exemple où cette fois on définit une fonction utilisateur.

import oparser.*;

public class Test3
{
  public static void main(String[] arg)
  {
    SUnaryFunction f = new SUnaryFunction("f","z","3*z-z*z");
    System.out.println("f(2) = "+f.eval(2));
    Parser parser = new Parser("2*f(x)*f(x)");
    parser.addVar("x");
    parser.addFunc(f);
    parser.parseString();
    parser.setVar("x",-2);
    System.out.println("2*f(-2)*f(-2) = "+parser.eval());
    }
}

Dans cet exemple, via la classe SUnaryFunction, on définit une fonction, dite utilisateur, par une chaine de caractères. Dans notre cas, on définit la fonction que l'on appelle "f", de variable "z" par f(z) = 3*z-z*z.

On affiche alors en premier lieu la valeur de f(2) par appel de la méthode eval() de la classe SUnaryFunction.

Ensuite on remarque qu'il est possible de faire prendre en compte notre fonction utilisateur "f" par une instance de la classe Parser. Il suffit pour cela, après avoir instancié un objet de type Parser, de lui indiquer les fonctions à reconnaitre grâce à la méthode addFunc(SUnaryFunction). Dans notre exemple on lui indique la fonction f. Ensuite comme précédemment on indique la variable (ici x : on note au passage la possibilité de définir une fonction de z et de l'utiliser par la suite comme une fonction d'une autre variable, ici x).

Pour finir on affiche le résultat avec la méthode eval() comme précédemment.

N'hesitez pas a donner votre avis ou à poser des questions sur ce sujet : mail

Opale Team : January 31 2004 23:14:10.