Implémentation d'un analyseur de syntaxe mathématique par méthode d'analyse syntaxique descendante récursive (Java)

Cela fait longtemps qu'Internet n'a pas été coupé au travail. J'ai essayé de donner au titre un nom dur qui ne semble pas être bien accueilli dans l'actuel Qiita

En raison des performances requises par les exigences, j'ai créé un analyseur qui calcule quatre règles à l'aide de la méthode d'analyse de la syntaxe descendante récursive. Je vais le laisser car cela peut être utile à quelqu'un

Exigences

Puisque la formule est obtenue sous forme de chaîne de caractères dans l'application batch, il semble qu'il ait voulu la calculer et renvoyer le résultat, mais le nombre était énorme. À l'origine, il semble qu'il ait eu l'intention d'appeler JavaScript depuis Java et de passer la formule telle quelle pour le calcul, mais il semble que cela ne se soit pas terminé en un jour car le nombre de formules cibles est de dizaines de milliers et de centaines de milliers.

De plus, il semble que le nombre augmentera régulièrement à l'avenir!

Bien sûr, il y a aussi le travail suivant, nous devons donc nous assurer que le processus est terminé à l'heure de début.

Alors je parlais de vouloir que je fasse quelque chose à ce sujet. Quand j'en ai entendu parler pour la première fois, j'ai pensé qu'il ne serait pas possible d'effectuer un traitement de calcul à grande vitesse avec JavaScript en appelant un programme externe.

Il vous suffit de créer un analyseur capable d'effectuer un calcul rapide à quatre règles. Il semble que vous souhaitiez également contrôler l'erreur d'arrondi au moment de la division, vous devez donc y penser également.

Eh bien, je m'attendais à ce qu'il n'y ait aucun problème en termes de vitesse si je l'implémentais entièrement en Java, j'ai donc décidé d'opter pour une méthode d'analyse syntaxique descendante récursive raisonnablement puissante au lieu d'une simple implémentation

code

Ce qui suit est implémenté dans Java 8

FormulaParser.java


import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class FormulaParser {
    private static final int HIGH_PRIORITY = 3;
    private static final int MID_PRIORITY = 2;
    private static final int LOW_PRIORITY = 1;
    private static final Pattern EMPTY_BRACKET = Pattern.compile("\\(\\)");
    private static final Pattern NOT_CLOSE_BRACKET = Pattern.compile("\\)\\(");
    private static final int NO_EXIST = -1;
    private static final String ZERO = "0";
    private static final String BRACKET_AND_ZERO = "(0";

    private String expression; //formule
    private FormulaParser left; //Nœud enfant gauche
    private FormulaParser right; //Nœud enfant droit
    private int scale;

    /**
     *Constructeur avec échelle
     ** Tenir compte de l'échelle uniquement en cas de division
     *
     * @formule d'expression param
     * @param scale Position décimale inférieure lors de la division
     */
    public FormulaParser(String expression, int scale) {
        this.expression = format(expression);
        this.scale = scale;
    }

    /**
     *Divisez la formule en deux et calculez
     *
     * @throws FormulaParseException
     */
    public String execute() throws FormulaParseException {
        //Retirez le support le plus extérieur
        String exp = delMostOuterBrackets(this.expression);
        //Trouvez l'opérateur de l'expression et obtenez la position
        int opePos = getOpePos(exp);
        //Si l'expression ne contient pas d'opérateur, elle est considérée comme un terme
        if (opePos < 0) {
            left = null;
            right = null;
            return new BigDecimal(exp).toPlainString();
        }
        //Traitement illégal si la position de l'opérateur est au début ou à la fin d'une expression
        if (opePos == 0 || opePos == exp.length() - 1) {
            throw new FormulaParseException(exp);
        }
        //Créez un nœud avec le côté gauche de l'opérateur comme sous-expression gauche
        left = new FormulaParser(exp.substring(0, opePos), scale);
        //Créez un nœud avec le côté droit de l'opérateur comme sous-expression droite
        right = new FormulaParser(exp.substring(opePos + 1), scale);
        //Définissez les opérateurs restants dans cette note
        expression = exp.substring(opePos, opePos + 1);
        return calculate(left.execute(), OPERATOR.getEnum(expression), right.execute(), scale);
    }

    /**
     *Obtenez la position de l'opérateur
     *
     * @expression de param exp
     * @retour de la position de l'opérateur(0 début)/Si non-Renvoie 1
     */
    private static int getOpePos(String exp) {
        int opePos = NO_EXIST;
        int curPriority = Integer.MAX_VALUE;
        int nest = 0;
        for (int i = 0, len = exp.length(); i < len; i++) {
            int priority = 0;
            switch (OPERATOR.getEnum(String.valueOf(exp.charAt(i)))) {
                case PLUS:
                case MINUS:
                    priority = MID_PRIORITY;
                    break;
                case MULTIPLY:
                case DIVIDE:
                    priority = HIGH_PRIORITY;
                    break;
                case LEFT_BRACKET:
                    nest++;
                    continue;
                case RIGHT_BRACKET:
                    nest--;
                    continue;
                default:
                    continue;
            }
            if (nest == 0 && priority <= curPriority) {
                curPriority = priority;
                opePos = i;
            }
        }
        return opePos;
    }

    /**
     *Traitement des calculs
     *
     * @param lExp Terme gauche
     * @opérateur ope param
     * @param rExp Terme correct
     * @échelle d'échelle param
     */
    private String calculate(String lExp, OPERATOR ope, String rExp, int scale) throws FormulaParseException {
        BigDecimal left = new BigDecimal(lExp);
        BigDecimal right = new BigDecimal(rExp);
        switch (ope) {
            case PLUS:
                return left.add(right).toPlainString();
            case MINUS:
                return left.subtract(right).toPlainString();
            case MULTIPLY:
                return left.multiply(right).toPlainString();
            case DIVIDE:
                return left.divide(right, scale, RoundingMode.DOWN).toPlainString();
            default:
                throw new FormulaParseException(left + ope.val + rExp);
        }
    }

    /**
     *format
     *L'espace demi-largeur est exclu
     *Puisqu'il est difficile de faire la distinction entre les symboles positifs et négatifs et les opérateurs d'addition / soustraction, remplissez 0 pour le rendre plus facile.
     *
     * @expression de param exp
     * @renvoie une expression formatée ex) -3 + 1 → 0-3+1
     */
    private static String format(String exp) {
        //Élimine les espaces demi-largeur
        StringBuilder e = new StringBuilder(exp.replaceAll(" ", ""));
        int cur = 0;
        for (; ; ) {
            int plusIndex = e.indexOf(OPERATOR.PLUS.val, cur);
            int minusIndex = e.indexOf(OPERATOR.MINUS.val, cur);
            if (plusIndex == NO_EXIST && minusIndex == NO_EXIST) {
                break;
            }
            //Obtenir l'index de l'opérateur existant et qui précède
            if (plusIndex < minusIndex) {
                cur = (plusIndex == NO_EXIST) ? minusIndex : plusIndex;
            } else {
                cur = (minusIndex == NO_EXIST) ? plusIndex : minusIndex;
            }
            if (cur == 0) {
                e.insert(cur, ZERO);
                cur = cur + ZERO.length() + 1;
                continue;
            }
            //Ajoutez 0 si le caractère avant l'opérateur n'est pas un nombre et n'est pas un opérateur de parenthèse fermante, de multiplication ou de division
            char preChar = e.charAt(cur - 1);
            if (!Character.isDigit(preChar)
                    && preChar != OPERATOR.RIGHT_BRACKET.cVal) {
                if (preChar == OPERATOR.MULTIPLY.cVal
                        || preChar == OPERATOR.DIVIDE.cVal
                        || preChar == OPERATOR.MINUS.cVal) {
                    int endDigits = 0;
                    for (int i = cur + 1, len = e.length(); i < len; i++) {
                        char c = e.charAt(i);
                        if (!Character.isDigit(c) && c != '.') {
                            break;
                        }
                        endDigits = i;
                    }
                    e.insert(cur, BRACKET_AND_ZERO).insert(endDigits + BRACKET_AND_ZERO.length() + 1, OPERATOR.RIGHT_BRACKET.cVal);
                    cur = endDigits + BRACKET_AND_ZERO.length();
                } else {
                    e.insert(cur, ZERO);
                    cur = cur + ZERO.length();
                }
            }
            cur++;
            if (cur > e.length()) break;
        }
        return e.toString();
    }

    /**
     *Processus de suppression des parenthèses
     *Supprimez les parenthèses les plus à l'extérieur de l'expression
     * (1+2)+(3+4)Renvoie une expression comme
     *Lancer une exception en tant qu'expression non valide si les parenthèses ne sont pas fermées
     *
     * @expression de param exp
     * @return Expression ex avec les parenthèses supprimées) (4*2) → 4*2,  ((3+4)) → 3+4, (1+2)+(3+4) → (1+2)+(3+4)
     * @throws FormulaParseException
     */
    private static String delMostOuterBrackets(String exp) throws FormulaParseException {
        if (matchFirst(exp, EMPTY_BRACKET).isPresent()) throw new FormulaParseException(exp);
        if (matchFirst(exp, NOT_CLOSE_BRACKET).isPresent()) throw new FormulaParseException(exp);
        if (exp.charAt(0) == OPERATOR.RIGHT_BRACKET.cVal) throw new FormulaParseException(exp);

        boolean hasMostOuterBrackets = false;
        int nest = 0;
        //Vérifiez le premier caractère
        if (exp.charAt(0) == OPERATOR.LEFT_BRACKET.cVal) {
            hasMostOuterBrackets = true;
            nest++;
        }
        //Vérifiez le premier caractère et les suivants caractère par caractère
        for (int i = 1, len = exp.length(); i < len; i++) {
            if (exp.charAt(i) == OPERATOR.LEFT_BRACKET.cVal) {
                nest++;
            } else if (exp.charAt(i) == OPERATOR.RIGHT_BRACKET.cVal) {
                nest--;
                if (nest == 0 && i < len - 1) {
                    hasMostOuterBrackets = false;
                }
            }
        }
        //Expression illégale si les parenthèses ne sont pas fermées
        if (nest != 0) throw new FormulaParseException(exp);
        //S'il n'y a pas de parenthèse, renvoyez-le tel quel
        if (!hasMostOuterBrackets) return exp;
        //Supprimer la première et la dernière parenthèses
        String ret = exp.substring(1, exp.length() - 1);
        //S'il y a encore des parenthèses, recommencez
        if (ret.charAt(0) == OPERATOR.LEFT_BRACKET.cVal
                && ret.charAt(ret.length() - 1) == OPERATOR.RIGHT_BRACKET.cVal) {
            return delMostOuterBrackets(ret);
        }
        return ret;
    }

    /**
     *Chercher
     *
     * @param s Cible de recherche
     * @expression régulière param p
     * @renvoyer les résultats de la recherche
     */
    private static Optional<String> matchFirst(String s, Pattern p) {
        Matcher m = p.matcher(s);
        return m.find() ? Optional.of(m.group(0)) : Optional.empty();
    }

    /**
     *opérateur
     */
    private enum OPERATOR {
        PLUS("+", '+'),
        MINUS("-", '-'),
        MULTIPLY("*", '*'),
        DIVIDE("/", '/'),
        LEFT_BRACKET("(", '('),
        RIGHT_BRACKET(")", ')'),
        NO_OPE(" ", ' ');

        public String val;
        public char cVal;
        private final static Map<String, OPERATOR> m = new HashMap<>();

        static {
            for (OPERATOR o : OPERATOR.values()) {
                m.put(o.val, o);
            }
        }

        private OPERATOR(String val, char cVal) {
            this.val = val;
            this.cVal = cVal;
        }

        public static OPERATOR getEnum(String val) {
            return m.getOrDefault(val, NO_OPE);
        }
    }
}

FormulaParseException.java


public class FormulaParseException extends Exception {
    public FormulaParseException(String msg) {
        super(msg);
    }
}

L'exception a implémenté quelque chose comme ça L'analyse parseur et le traitement des calculs ne sont pas séparés et sont combinés en une seule classe. Comme il est difficile de faire la distinction entre les symboles positifs et négatifs et les opérateurs d'addition / soustraction, il est rempli de 0. C'est aussi un point pour ajouter des parenthèses au besoin

L'analyse coûte également beaucoup, donc l'application d'origine a beaucoup de pré-vérifications. De plus, je rend possible le traitement des fonctions et des variables mathématiques, mais je l'ai omis car il est difficile de se souvenir et d'écrire du code. La méthode matchFirst () est un vestige de cela J'ai implémenté d'autres utilitaires utiles et fait diverses choses

Tout ce que vous avez à faire est de remplacer les variables de manière appropriée Quant à la fonction Math, juste pour donner un indice, la fonction Math est traitée comme un terme dans le code ci-dessus. Ainsi, dans le code ci-dessous, vous devez déterminer s'il s'agit d'une fonction Math et appeler la méthode qui la traite s'il s'agit d'une fonction Math. return new BigDecimal(exp).toPlainString();

La méthode qui traite la fonction Math doit être traitée en vérifiant régulièrement les caractères comme delMostOuterBrackets () et format (). En d'autres termes, vous pouvez appliquer le code écrit dans l'article, donc si nécessaire, essayez de le créer vous-même.

À la fin

Pour le moment, je l'ai implémenté et essayé, et il répondait aux exigences, donc ça s'arrête là Il est suspect que le nombre de cas passe de dizaines de millions à 100 millions, mais il semble que cela n'ira pas aussi loin, donc ça semble bien

J'ai écrit beaucoup de tests, mais je vais l'omettre car il est difficile de s'en souvenir et de le porter Eh bien, je n'ai même pas besoin de JUnit car je vérifie simplement le résultat attendu de l'expression.

J'apprends par moi-même, pas en me spécialisant en CS, il était donc très utile de réfléchir attentivement à ce type de conception et de mise en œuvre dans la pratique.

Aussi, j'espère qu'il y aura des projets qui ne pourront être jumelés sans connaissance des algorithmes et des structures de données, et l'article est terminé.

Noshi

Recommended Posts

Implémentation d'un analyseur de syntaxe mathématique par méthode d'analyse syntaxique descendante récursive (Java)
[Java twig] Créer un combinateur d'analyseur pour l'analyse syntaxique de descente récursive
[Java twig] Créer un combinateur d'analyseur pour une analyse de syntaxe descendante récursive (également prendre des notes)
Avez-vous besoin d'une implémentation de Java compatible avec la mémoire?
Histoire de créer une application de gestion de tâches avec Swing, Java
[Java] Implémentation du réseau Faistel
Implémentation de XLPagerTabStrip avec TabBarController
[Java] Simplifiez la mise en œuvre de la gestion de l'historique des données avec Reladomo
Résumé de la classe Java Math
Analyse HTML (scraping) avec JAVA
Implémentation Java de tri-tree
Créons une application TODO en Java 4 Implémentation de la fonction de publication
Créons une application TODO en Java 6 Implémentation de la fonction de recherche
Créons une application TODO en Java 8 Implémentation des fonctions d'édition
[Détails] Implémentation d'applications grand public avec Kinesis Client Library for Java
Une histoire sur l'utilisation de l'API League Of Legends avec JAVA
[Illustration] Recherche de la somme des pièces avec une fonction récursive [Ruby]
Pensez à une stratégie de mise à jour Java
Construire un projet Java avec Gradle
Une brève description des dépendances JAVA
Implémentation d'une fonction similaire en Java
Obtenir une liste de fichiers S3 avec ListObjectsV2Request (AWS SDK for Java)
Un enregistrement de la configuration d'un environnement de développement Java avec Visual Studio Code
L'histoire de la création d'un lanceur de jeu avec une fonction de chargement automatique [Java]
Exprimons le résultat de l'analyse du code d'octet Java dans un diagramme de classes
Implémentation de la méthode de clonage pour Java Record
Implémentation de DBlayer en Java (RDB, MySQL)
Nommer un groupe d'expressions régulières (Java)
[Swift 5] Implémentation de l'enregistrement des membres dans Firebase
Extraire une partie d'une chaîne en Ruby
Diviser une chaîne avec ". (Dot)" en Java
Présentation du test Java automatisé avec JUnit 5 + Gradle
Une histoire confirmant l'implémentation de la bibliothèque Java SendGrid lorsque la livraison du courrier échoue
Valider le jeton d'ID d'un utilisateur authentifié par AWS Cognito en Java