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