Es ist lange her, dass das Internet bei der Arbeit abgeschnitten wurde. Ich habe versucht, dem Titel einen harten Namen zu geben, der in der aktuellen Qiita nicht gut aufgenommen zu werden scheint
Aufgrund der von den Anforderungen geforderten Leistung habe ich einen Analysator erstellt, der vier Regeln mithilfe der Methode der rekursiven absteigenden Syntaxanalyse berechnet. Ich lasse es, da es für jemanden hilfreich sein kann
Da die Formel in der Stapelanwendung als Zeichenfolge erhalten wird, wollte er sie anscheinend berechnen und das Ergebnis zurückgeben, aber die Anzahl war riesig. Ursprünglich schien er beabsichtigt zu haben, JavaScript von Java aus aufzurufen und die Formel so zu übergeben, wie sie für die Berechnung ist, aber es scheint, dass sie nicht an einem Tag beendet wurde, da die Anzahl der Zielformeln Zehntausende und Hunderttausende beträgt.
Darüber hinaus scheint die Zahl in Zukunft stetig zu steigen!
Natürlich gibt es auch den nächsten Job, also müssen wir sicherstellen, dass der Prozess zum Startzeitpunkt abgeschlossen ist.
Also habe ich darüber gesprochen, dass ich etwas dagegen tun soll. Als ich zum ersten Mal davon hörte, dachte ich, dass es nicht möglich wäre, eine Hochgeschwindigkeitsberechnungsverarbeitung mit JavaScript durch Aufrufen eines externen Programms durchzuführen.
Sie müssen nur einen Analysator erstellen, der eine Hochgeschwindigkeitsberechnung mit vier Regeln durchführen kann. Es scheint, dass Sie auch den Rundungsfehler zum Zeitpunkt der Division kontrollieren möchten, also müssen Sie auch darüber nachdenken
Nun, ich hatte erwartet, dass es kein Problem mit der Geschwindigkeit geben würde, wenn ich alles in Java implementieren würde, also entschied ich mich für eine einigermaßen leistungsfähige Methode zur Analyse rekursiver absteigender Syntax anstelle einer einfachen Implementierung.
Folgendes ist in Java 8 implementiert
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; //Formel
private FormulaParser left; //Linker untergeordneter Knoten
private FormulaParser right; //Rechter untergeordneter Knoten
private int scale;
/**
*Konstruktor mit Skala
** Skalierung nur bei Teilung berücksichtigen
*
* @Parameterausdrucksformel
* @Parameterskala Abgerundete Dezimalstelle beim Teilen
*/
public FormulaParser(String expression, int scale) {
this.expression = format(expression);
this.scale = scale;
}
/**
*Teilen Sie die Formel in zwei Hälften und berechnen Sie
*
* @throws FormulaParseException
*/
public String execute() throws FormulaParseException {
//Entfernen Sie die äußerste Halterung
String exp = delMostOuterBrackets(this.expression);
//Suchen Sie den Operator aus dem Ausdruck und ermitteln Sie die Position
int opePos = getOpePos(exp);
//Wenn der Ausdruck keinen Operator enthält, wird er als Begriff betrachtet
if (opePos < 0) {
left = null;
right = null;
return new BigDecimal(exp).toPlainString();
}
//Unzulässige Behandlung, wenn sich die Bedienerposition am Anfang oder Ende eines Ausdrucks befindet
if (opePos == 0 || opePos == exp.length() - 1) {
throw new FormulaParseException(exp);
}
//Erstellen Sie einen Knoten mit der linken Seite des Operators als linkem Unterausdruck
left = new FormulaParser(exp.substring(0, opePos), scale);
//Erstellen Sie einen Knoten mit der rechten Seite des Operators als rechtem Unterausdruck
right = new FormulaParser(exp.substring(opePos + 1), scale);
//Stellen Sie die verbleibenden Operatoren in diesem Hinweis ein
expression = exp.substring(opePos, opePos + 1);
return calculate(left.execute(), OPERATOR.getEnum(expression), right.execute(), scale);
}
/**
*Holen Sie sich die Position des Bedieners
*
* @param exp Ausdruck
* @Bedienerposition zurückgeben(0 Anfang)/Wenn nicht-Rückgabe 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;
}
/**
*Berechnungsverarbeitung
*
* @param lExp Linker Begriff
* @Parameteroperator
* @param rExp Richtiger Begriff
* @Param Scale Scale
*/
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
*Raum mit halber Breite ist ausgeschlossen
*Da es schwierig ist, zwischen positiven und negativen Symbolen und Additions- / Subtraktionsoperatoren zu unterscheiden, geben Sie 0 ein, um dies zu vereinfachen.
*
* @param exp Ausdruck
* @Rückgabe des formatierten Ausdrucks z) -3 + 1 → 0-3+1
*/
private static String format(String exp) {
//Beseitigen Sie Leerzeichen mit halber Breite
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;
}
//Index abrufen, welcher Operator vorhanden ist und vorangestellt ist
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;
}
//Fügen Sie 0 hinzu, wenn das Zeichen unmittelbar vor dem Operator keine Zahl und kein schließender Klammer-, Multiplikations- oder Divisionsoperator ist
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();
}
/**
*Löschvorgang in Klammern
*Entfernen Sie die äußersten Klammern aus dem Ausdruck
* (1+2)+(3+4)Gibt einen Ausdruck wie zurück
*Wirf eine Ausnahme als ungültigen Ausdruck aus, wenn die Klammern nicht geschlossen sind
*
* @param exp Ausdruck
* @return Expression ex mit entfernten Klammern) (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;
//Überprüfen Sie das erste Zeichen
if (exp.charAt(0) == OPERATOR.LEFT_BRACKET.cVal) {
hasMostOuterBrackets = true;
nest++;
}
//Überprüfen Sie das erste und die folgenden Zeichen zeichenweise
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;
}
}
}
//Unzulässiger Ausdruck, wenn Klammern nicht geschlossen sind
if (nest != 0) throw new FormulaParseException(exp);
//Wenn keine Klammer vorhanden ist, geben Sie sie unverändert zurück
if (!hasMostOuterBrackets) return exp;
//Entfernen Sie die erste und letzte Klammer
String ret = exp.substring(1, exp.length() - 1);
//Wenn noch Klammern vorhanden sind, erneut verarbeiten
if (ret.charAt(0) == OPERATOR.LEFT_BRACKET.cVal
&& ret.charAt(ret.length() - 1) == OPERATOR.RIGHT_BRACKET.cVal) {
return delMostOuterBrackets(ret);
}
return ret;
}
/**
*Suche
*
* @param s Suchziel
* @param p regulärer Ausdruck
* @Suchergebnisse zurückgeben
*/
private static Optional<String> matchFirst(String s, Pattern p) {
Matcher m = p.matcher(s);
return m.find() ? Optional.of(m.group(0)) : Optional.empty();
}
/**
*Operator
*/
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);
}
}
Die Ausnahme hat so etwas implementiert Parseranalyse und Berechnungsverarbeitung werden nicht getrennt und in einer Klasse zusammengefasst. Da es schwierig ist, zwischen positiven und negativen Symbolen und Additions- / Subtraktionsoperatoren zu unterscheiden, wird es mit 0 gefüllt. Es ist auch ein Punkt, nach Bedarf Klammern hinzuzufügen
Da die Analyse auch einen bestimmten Betrag kostet, muss der ursprüngliche Antrag vorab überprüft werden. Ich mache es auch möglich, mathematische Funktionen und Variablen zu verarbeiten, aber ich habe es weggelassen, weil es schwierig ist, sich Code zu merken und ihn zu schreiben. Die Methode matchFirst () ist ein Rest davon Ich habe andere nützliche Dienstprogramme implementiert und verschiedene Dinge getan
Sie müssen lediglich die Variablen entsprechend ersetzen
Um einen Hinweis zu geben, wird die Math-Funktion im obigen Code als Begriff behandelt.
Im folgenden Code sollten Sie also feststellen, ob es sich um eine Math-Funktion handelt, und die Methode aufrufen, die sie verarbeitet, wenn es sich um eine Math-Funktion handelt.
return new BigDecimal(exp).toPlainString();
Die Methode, die die Math-Funktion verarbeitet, sollte verarbeitet werden, indem die Zeichen wie "delMostOuterBrackets ()" und "format ()" ständig überprüft werden. Mit anderen Worten, Sie können den im Artikel geschriebenen Code anwenden. Versuchen Sie also, ihn bei Bedarf selbst zu erstellen.
Vorerst habe ich es implementiert und ausprobiert, und es hat die Anforderungen erfüllt, sodass es dort endet Es ist verdächtig, wenn die Anzahl der Fälle von zehn Millionen auf 100 Millionen steigt, aber es scheint, dass es nicht so weit gehen wird, also scheint es in Ordnung zu sein
Ich habe viele Tests geschrieben, aber ich werde es weglassen, weil es schwierig ist, sich daran zu erinnern und es zu portieren Nun, ich brauche nicht einmal JUnit, weil ich nur das erwartete Ergebnis des Ausdrucks überprüfe.
Ich lerne alleine, nicht durch das Hauptfach CS, daher war es sehr hilfreich, über diese Art von Design und Implementierung in der Praxis sorgfältig nachzudenken.
Ich hoffe auch, dass es Projekte geben wird, die ohne Kenntnis von Algorithmen und Datenstrukturen nicht abgeglichen werden können, und der Artikel ist beendet.
Noshi
Recommended Posts