Comment évaluer une expression mathématique donnée sous forme de chaîne de caractères?

Question

Je suis en train d'essayer d'écrire une routine en Java pour évaluer des expressions mathématiques à partir de valeurs String comme :

1. "5+3"
2. "10-4*5"
3. "(1+10)*3"

Je veux éviter beaucoup de déclarations if-then-else. Comment puis-je faire cela?

Answer 1

Avec JDK1.6, vous pouvez utiliser le moteur JavaScript intégré.

import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;
import javax.script.ScriptException;

public class Test {
  public static void main(String[] args) throws ScriptException {
    ScriptEngineManager mgr = new ScriptEngineManager();
    ScriptEngine engine = mgr.getEngineByName("JavaScript");
    String foo = "40+2";
    System.out.println(engine.eval(foo));
    } 
}

Answer 2

J'ai écrit cette méthode eval pour les expressions arithmétiques pour répondre à cette question. Elle effectue des additions, des soustractions, des multiplications, des divisions, des exposants (en utilisant le symbole ^), et quelques fonctions de base telles que sqrt. Elle prend en charge les groupes en utilisant (...), et elle respecte les règles de précédence et d'associativité des opérateurs correctement.

public static double eval(final String str) {
    return new Object() {
        int pos = -1, ch;

        void nextChar() {
            ch = (++pos < str.length()) ? str.charAt(pos) : -1;
        }

        boolean eat(int charToEat) {
            while (ch == ' ') nextChar();
            if (ch == charToEat) {
                nextChar();
                return true;
            }
            return false;
        }

        double parse() {
            nextChar();
            double x = parseExpression();
            if (pos < str.length()) throw new RuntimeException("Inattendu : " + (char)ch);
            return x;
        }

        // Grammaire:
        // expression = term | expression `+` term | expression `-` term
        // term = factor | term `*` factor | term `/` factor
        // factor = `+` factor | `-` factor | `(` expression `)` | number
        //        | functionName `(` expression `)` | functionName factor
        //        | factor `^` factor

        double parseExpression() {
            double x = parseTerm();
            for (;;) {
                if      (eat('+')) x += parseTerm(); // addition
                else if (eat('-')) x -= parseTerm(); // soustraction
                else return x;
            }
        }

        double parseTerm() {
            double x = parseFactor();
            for (;;) {
                if      (eat('*')) x *= parseFactor(); // multiplication
                else if (eat('/')) x /= parseFactor(); // division
                else return x;
            }
        }

        double parseFactor() {
            if (eat('+')) return +parseFactor(); // plus unaire
            if (eat('-')) return -parseFactor(); // moins unaire

            double x;
            int startPos = this.pos;
            if (eat('(')) { // parenthèses
                x = parseExpression();
                if (!eat(')')) throw new RuntimeException("Manquant ')'");
            } else if ((ch >= '0' && ch <= '9') || ch == '.') { // nombres
                while ((ch >= '0' && ch <= '9') || ch == '.') nextChar();
                x = Double.parseDouble(str.substring(startPos, this.pos));
            } else if (ch >= 'a' && ch <= 'z') { // fonctions
                while (ch >= 'a' && ch <= 'z') nextChar();
                String func = str.substring(startPos, this.pos);
                if (eat('(')) {
                    x = parseExpression();
                    if (!eat(')')) throw new RuntimeException("Manquant ')' après l'argument de " + func);
                } else {
                    x = parseFactor();
                }
                if (func.equals("sqrt")) x = Math.sqrt(x);
                else if (func.equals("sin")) x = Math.sin(Math.toRadians(x));
                else if (func.equals("cos")) x = Math.cos(Math.toRadians(x));
                else if (func.equals("tan")) x = Math.tan(Math.toRadians(x));
                else throw new RuntimeException("Fonction inconnue : " + func);
            } else {
                throw new RuntimeException("Inattendu : " + (char)ch);
            }

            if (eat('^')) x = Math.pow(x, parseFactor()); // exponentiation

            return x;
        }
    }.parse();
}

Exemple :

System.out.println(eval("((4 - 2^3 + 1) * -sqrt(3*3+4*4)) / 2"));

Sortie : 7.5 (ce qui est correct)

---

Le parseur est un analyseur syntaxique descendant récursif, qui utilise internalement des méthodes de parse distinctes pour chaque niveau de précédence d'opérateur dans sa grammaire. Je l'ai délibérément gardé court, mais voici quelques idées pour l'étendre :

• Variables :

  La partie du parseur qui lit les noms des fonctions peut facilement être modifiée pour gérer également des variables personnalisées, en recherchant les noms dans une table de variables transmise à la méthode eval, comme une Map variables.

• Compilation et évaluation séparées :

  Et si, après avoir ajouté la prise en charge des variables, vous vouliez évaluer la même expression des millions de fois avec des variables modifiées, sans la reparser à chaque fois? C'est possible. Définissez d'abord une interface à utiliser pour évaluer l'expression précompilée :

    @FunctionalInterface
    interface Expression {
        double eval();
    }

  Maintenant, pour retravailler la fonction "eval" d'origine en une fonction "parse", modifiez toutes les méthodes qui renvoient des double, pour qu'elles renvoient plutôt une instance de cette interface. La syntaxe lambda de Java 8 fonctionne bien pour cela. Exemple d'une des méthodes modifiées :

    Expression parseExpression() {
        Expression x = parseTerm();
        for (;;) {
            if (eat('+')) { // addition
                Expression a = x, b = parseTerm();
                x = (() -> a.eval() + b.eval());
            } else if (eat('-')) { // soustraction
                Expression a = x, b = parseTerm();
                x = (() -> a.eval() - b.eval());
            } else {
                return x;
            }
        }
    }

  Cela crée un arbre récursif d'objets Expression représentant l'expression compilée (un arbre syntaxique abstrait). Ensuite, vous pouvez la compiler une fois et l'évaluer plusieurs fois avec des valeurs différentes :

    public static void main(String[] args) {
        Map variables = new HashMap<>();
        Expression exp = parse("x^2 - x + 2", variables);
        for (double x = -20; x <= +20; x++) {
            variables.put("x", x);
            System.out.println(x + " => " + exp.eval());
        }
    }

• Différents types de données :

  Au lieu de double, vous pourriez modifier l'évaluateur pour utiliser quelque chose de plus puissant comme BigDecimal, ou une classe qui implémente des nombres complexes, ou des nombres rationnels (fractions). Vous pourriez même utiliser Object, permettant une certaine mixité de types de données dans les expressions, tout comme un véritable langage de programmation. :)

---

_{Tout le code de cette réponse est publié dans le <a href="https://creativecommons.org/publicdomain/zero/1.0/" rel="noreferrer">domaine public</a>. Amusez-vous bien !}

Answer 3

J'ai récemment écrit un analyseur d'expressions mathématiques appelé exp4j que j'ai publié sous la licence Apache. Vous pouvez le consulter ici :

http://www.objecthunter.net/exp4j/

Answer 4

La bonne façon de résoudre cela est avec un analyseur lexical et un analyseur syntaxique. Vous pouvez écrire des versions simplifiées de ceux-ci vous-même, ou ces pages ont aussi des liens vers des analyseurs lexicaux et syntaxiques en Java.

Créer un analyseur descendant récursif est un très bon exercice d'apprentissage.

Answer 5

ICI se trouve une autre bibliothèque open source sur GitHub nommée EvalEx.

Contrairement au moteur JavaScript, cette bibliothèque est axée uniquement sur l'évaluation d'expressions mathématiques. De plus, la bibliothèque est extensible et supporte l'utilisation d'opérateurs booléens ainsi que des parenthèses.