・ Da es sich um einen Oleore-Algorithmus handelt, kann die Argumentation in erster Linie seltsam sein ・ Kleine Erklärung (Quelle und Kommentare lesen) ・ Tauchen Sie ein
In dem Dienst, den ich jetzt mache, gibt es einen Bildschirm, auf dem der Benutzer die Berechnungsformel eingeben kann. Daher musste die Einrückungsnotation in die inverse polnische Notation konvertiert, gespeichert und berechnet werden.
Java 1.8 Spring 4.x
Erstellen Sie eine Knotenklasse zur Verwendung in Syntaxbäumen und Arrays.
Node.java
public class Node{
protected Node left;
protected Node right;
protected Node parent;
protected String data;
protected Integer precedence;
protected boolean visited;
public Node(String data, int precedence) {
this.data = data;
this.precedence = precedence;
this.setVisited(false);
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
left.setParent(this);
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
right.setParent(this);
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public int getPrecede() {
return precedence;
}
public void setPrecede(int precedence) {
this.precedence = precedence;
}
public Node searchTop() {
Node current = this;
while(current.getParent() != null) {
current = current.getParent();
}
return current;
}
public Node clone() {
return new Node(this.data, this.precedence);
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
}
Eine Klasse, die einen Knoten eines dichotomisierten Baums darstellt. Es enthält einen Verweis auf den Knoten am Ende des linken und rechten Zweigs und den übergeordneten Knoten.
Analysieren Sie die neutrale Notation, generieren Sie den Syntaxbaum und konvertieren Sie in die inverse polnische Notation. Es ist ein Code, der nach Versuch und Irrtum erstellt wurde, also ziemlich rau. Ich kenne die Theorie der Graphen nicht.
Formula.java
public class Formula {
//String-Konstante für reguläre Ausdrücke
//Raum
public static final String REGEXP_FORMAT = "(%s)";
public static final String WHITE_SPACE = "\\s";
//Ganzzahlen, Variablen, Anzahl der Dezimalstellen (verschiedene noch nicht berücksichtigt)
public static final String OPERANDS = "\\d\\.\\d|\\d|\\w";
//Eine Liste der Operatoren
public static final String OPERATORS = "\\+|\\-|\\*|\\/|%|\\^";
//Klammern
public static final String BRACKETS = "\\(|\\)";
//Halterung öffnen
public static final String OPENING_BRACKET = "\\(";
//Klammer schließen
public static final String CLOSING_BRACKET = "\\)";
public static final String MINUS = "-";
//
public static final String VALID_FORMULA = "^(\\d\\.\\d|\\d|\\w|-\\d\\.\\d|-\\d|-\\w)(((\\+|\\-|\\*|\\/|%|\\^)(\\d\\.\\d|\\d|\\w|-\\d\\.\\d|-\\d|-\\w))*)$";
//Koeffizient zur Berechnung negativer Werte
public static final String COEFFICIENT = "-1";
public static final String MULTIPLY = "*";
//Erhöhen Sie die Priorität des Bedieners in Klammern
public static final int INFLATE_NUMBER = 10;
//Vom Benutzer eingegebene Formel
private String formula;
//Syntaxbaumwurzel
private Node tree;
//Anordnung der umgekehrten polnischen Notation
private List<Node> rpn;
//Prioritätskarte für jeden Operator und Operanden
private static final Map<String, ValidCharacter> VALID_CHARACTERS_MAP
= Arrays.asList(
new ValidCharacter("\\d\\.\\d", Integer.MAX_VALUE - 1),
new ValidCharacter("\\w", Integer.MAX_VALUE - 1),
new ValidCharacter("\\d", Integer.MAX_VALUE - 1),
new ValidCharacter("%", 2),
new ValidCharacter("\\+", 2),
new ValidCharacter("\\-", 2),
new ValidCharacter("\\*", 3),
new ValidCharacter("\\/", 3),
new ValidCharacter("\\^", 4),
new ValidCharacter("\\(", 10),
new ValidCharacter("\\)", 10))
.stream().collect(Collectors.toMap(ValidCharacter::getData, d -> d));
//Warteschlange zum Speichern von Operatoren und Operanden in neutraler Notation
private Deque<Node> queue = new ArrayDeque<>();
//Konstrukteur
public Formula() {
}
public Formula(String formula) {
this.formula = formula;
}
public Node parseFormula() throws IllegalArgumentException {
return parseFormula(formula);
}
//Konvertieren Sie die neutrale Notation in die polnische Notation
public Node parseFormula(String formula) throws IllegalArgumentException {
//Entfernen Sie zusätzlichen Platz
String trim = formula.replaceAll(getRegExp(WHITE_SPACE), "");
//Ob es zusätzliche Zeichen enthält
String temp = trim.replaceAll(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");
Assert.isTrue(temp.length() == 0, "");
int bracket = 0;
//Zerlegen Sie eine Zeichenfolgenformel in Operatoren und Operanden
while(trim.length() > 0) {
//Extrahieren Sie den ersten Operator oder Operanden
String flagment = getFlagment(trim);
//Löschen Sie das entfernte Teil
trim = trim.replaceFirst(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");
//Extrahieren Sie das passende ValidCharacter aus der Prioritätszuordnung
ValidCharacter vc = VALID_CHARACTERS_MAP.entrySet().stream().filter(
entry -> {
return flagment.matches(entry.getKey());
}
).findFirst().get().getValue();
Assert.isTrue(vc != null, "");
//Erhöhen Sie bei offenen Klammern die Priorität
if(flagment.matches(OPENING_BRACKET)) {
bracket++;
continue;
}
//Verringern Sie die Priorität zum Schließen von Klammern
else if(flagment.matches(CLOSING_BRACKET)) {
bracket--;
continue;
}
String test_flagment = getFlagment(trim);
//Wenn ein negativer Wert enthalten ist-Durch Multiplikation durch 1 ersetzen
if((queue.isEmpty() || queue.peekLast().getData().matches(getRegExp(OPERATORS))) && MINUS.equals(flagment) && (test_flagment.matches(getRegExp(OPERANDS)))) {
queue.add(new Node(COEFFICIENT, Integer.MAX_VALUE - 1));
queue.add(new Node(MULTIPLY, 3 + INFLATE_NUMBER * (bracket + 1)));
}
//Wenn es sich um einen positiven Wert handelt, speichern Sie ihn unverändert in der Warteschlange
else {
queue.add(new Node(flagment, flagment.matches(getRegExp(OPERANDS))?vc.getPrecedence():(vc.getPrecedence() + INFLATE_NUMBER * bracket)));
}
}
//Überprüfen Sie, ob die Formel mit einem Operanden beginnt und mit einem Operator dazwischen endet
Assert.isTrue(String.join("", queue.stream().map(node -> node.getData()).collect(Collectors.toList())).matches(VALID_FORMULA), "");
//Machen Sie das erste Element der Warteschlange zum Stamm des Syntaxbaums
Node currentNode = queue.pollFirst();
//Syntaxbaum generieren
currentNode.setLeft(new Node("", Integer.MAX_VALUE));
currentNode.setRight(new Node("", Integer.MAX_VALUE));
do {
//Extrahieren Sie den Anfang der Warteschlange
Node poll = queue.pollFirst();
Assert.isTrue(bracket > 0 || !")".equals(poll.getData()), "");
Node left = currentNode, right = null;
//Suchen Sie, bis Sie einen Knoten mit einer höheren Priorität als den extrahierten Knoten finden
do {
//Wenn ein Knoten mit hoher Priorität gefunden wird
if(currentNode.getPrecede() >= poll.getPrecede()) {
left = currentNode;
right = new Node("", Integer.MAX_VALUE);
if(currentNode.getParent() != null) {
currentNode.getParent().setRight(poll);
}
currentNode = poll;
break;
}
//Gehen Sie bei Knoten mit niedriger Priorität einen rechts neben dem Zweig nach unten
else if(currentNode.getPrecede() < poll.getPrecede()) {
currentNode = currentNode.getRight();
}
}while(true);
//Knoten in Baum einfügen
currentNode.setLeft(left);
currentNode.setRight(right);
currentNode = currentNode.searchTop();
}while(!queue.isEmpty());
setTree(currentNode.searchTop());
return getTree();
}
//Extrahieren Sie den Anfang aus der Formel der Zeichenfolge
public String getFlagment(String formula) {
return formula.substring(0, formula.length() - formula.replaceFirst(getRegExp(OPERANDS, OPERATORS, BRACKETS), "").length());
}
public List<Node> toTreeToRpn() {
return parseTreeToRpn(this.tree);
}
//Konvertieren Sie den Syntaxbaum in ein Array in umgekehrter polnischer Notation
public List<Node> parseTreeToRpn(Node tree) {
//Zum Schluss drehen
rpn = new ArrayList<>();
Stack<Node> stack = new Stack<>();
stack.push(tree);
while(!stack.isEmpty() ) {
//Speichern Sie die Knoten im Stapel in einem Array
Node node = stack.pop();
rpn.add(node);
//Der Blattknoten ist Integer.MAX_Da es sich um einen WERT handelt, werden der linke und der rechte Zweig des Knotens mit einer niedrigeren Priorität im Stapel gespeichert.
if(node.getRight().getPrecede() < Integer.MAX_VALUE) {
stack.push(node.getRight());
}
if(node.getLeft().getPrecede() < Integer.MAX_VALUE) {
stack.push(node.getLeft());
}
}
Collections.reverse(rpn);
return rpn;
}
public int calculateRpnInteger() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
return calculateRpnInteger(this.rpn);
}
//Berechnen Sie die Formel für die inverse polnische Notation
public int calculateRpnInteger(List<Node> rpn) throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Stack<Node> stack = new Stack<>();
Calculator calc = new Calculator();
//Schleife für alle Elemente des Arrays
for(Node token : rpn) {
//Wenn es sich um einen Operanden handelt, wird er auf den Stapel geladen.
if(token.getPrecede() == Integer.MAX_VALUE - 1) {
stack.push(token);
}
//Nehmen Sie für den Operator den Binärwert aus dem Stapel und berechnen Sie
else {
Assert.notEmpty(stack, "");
Node left = stack.pop();
Assert.notEmpty(stack, "");
Node right = stack.pop();
stack.push(new Node(calc.calculate(token.getData(), left.getData(), right.getData()).toString(), Integer.MAX_VALUE - 1));
}
}
//Gibt das Berechnungsergebnis zurück
return Integer.valueOf(stack.pop().getData());
}
public String getFormula() {
return formula;
}
public void setFormula(String formula) {
this.formula = formula;
}
public Node getTree() {
return tree;
}
public void setTree(Node tree) {
this.tree = tree;
}
public String getRegExp(String... regexp) {
return String.format(REGEXP_FORMAT, String.join("|", regexp));
}
public List<Node> getRpn() {
return rpn;
}
public void setRpn(List<Node> rpn) {
this.rpn = rpn;
}
}
//Innere Klasse, die die Priorität von Operatoren und Operanden darstellt
class ValidCharacter {
String data;
Integer precedence;
public ValidCharacter(String data, int precedence) {
this.data = data;
this.precedence = precedence;
}
public String getData() {
return data;
}
public int getPrecedence() {
return precedence;
}
}
Die Reihenfolge der inversen polnischen Notation wird von Anfang an herausgenommen und nacheinander berechnet.
Calculator.java
public class Calculator {
private String key;
private Map<String, Method> calculators = new HashMap<>();
//Speichern Sie die Berechnungsmethode für jeden Operator in der Hash-Map.
public Calculator() throws NoSuchMethodException, SecurityException {
calculators.put("+", this.getClass().getMethod("addInteger", new Class[] {String.class, String.class}));
calculators.put("-", this.getClass().getMethod("subtractInteger", new Class[] {String.class, String.class}));
calculators.put("*", this.getClass().getMethod("multiplyInteger", new Class[] {String.class, String.class}));
calculators.put("/", this.getClass().getMethod("divideInteger", new Class[] {String.class, String.class}));
calculators.put("%", this.getClass().getMethod("surplusInteger", new Class[] {String.class, String.class}));
calculators.put("^", this.getClass().getMethod("powerFloat", new Class[] {String.class, String.class}));
}
//Führen Sie die Berechnung durch, indem Sie den Operator und zwei Operanden übergeben.
public Object calculate(String operator, String left, String right) throws IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Method method = calculators.get(operator);
Assert.isNotNull(method, "");
return method.invoke(this, left, right);
}
//Zusatz
public Object addInteger(String left, String right) {
return Integer.parseInt(left) + Integer.parseInt(right);
}
//Subtraktion
public Object subtractInteger(String left, String right) {
return Integer.parseInt(left) - Integer.parseInt(right);
}
//Multiplikation
public Object multiplyInteger(String left, String right) {
return Integer.parseInt(left) * Integer.parseInt(right);
}
//Teilung
public Object divideInteger(String left, String right) {
return Integer.parseInt(left) / Integer.parseInt(right);
}
//Überschuss
public Object surplusInteger(String left, String right) {
return Integer.parseInt(left) % Integer.parseInt(right);
}
//Leistung
public Object powerFloat(String left, String right) {
return (int)Math.pow(Double.parseDouble(left), Double.parseDouble(right));
}
}
Dies ist eine Klasse, die einfach berechnet wird, sodass keine Erklärung erforderlich ist.
Wenden Sie einige Formeln an und testen Sie, ob es wie erwartet funktioniert. Lassen Sie mich wissen, ob es Testfälle gibt, die nicht funktionieren.
FormulaTest.java
public class FormulaTest {
@Test
public void testGetFlagment() {
assertEquals("1", new Formula("1+1").getFlagment("1+1"));
}
@Test
public void testParseFormula1() {
Node node = new Formula().parseFormula("1+2");
assertEquals("1", node.getLeft().getData());
assertEquals("+", node.getData());
assertEquals("2", node.getRight().getData());
}
@Test
public void testParseFormula2() {
Node node = new Formula().parseFormula("(1+2)*3");
assertEquals("1", node.getLeft().getLeft().getData());
assertEquals("2", node.getLeft().getRight().getData());
assertEquals("+", node.getLeft().getData());
assertEquals("3", node.getRight().getData());
assertEquals("*", node.getData());
}
@Test
public void testParseFormula3() {
Node node = new Formula().parseFormula("3*(1+2)");
assertEquals("1", node.getRight().getLeft().getData());
assertEquals("2", node.getRight().getRight().getData());
assertEquals("+", node.getRight().getData());
assertEquals("3", node.getLeft().getData());
assertEquals("*", node.getData());
}
@Test
public void testParseFormula4() {
Node node = new Formula().parseFormula("(1+2)*(3+4)");
assertEquals("1", node.getLeft().getLeft().getData());
assertEquals("2", node.getLeft().getRight().getData());
assertEquals("+", node.getLeft().getData());
assertEquals("*", node.getData());
assertEquals("3", node.getRight().getLeft().getData());
assertEquals("4", node.getRight().getRight().getData());
assertEquals("+", node.getRight().getData());
}
@Test
public void testParseTreeToRPN1() {
Node node = new Formula().parseFormula("(1+2)*(3+4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
assertEquals("4", rpn.get(0).getData());
assertEquals("3", rpn.get(1).getData());
assertEquals("+", rpn.get(2).getData());
assertEquals("2", rpn.get(3).getData());
assertEquals("1", rpn.get(4).getData());
assertEquals("+", rpn.get(5).getData());
assertEquals("*", rpn.get(6).getData());
}
@Test
public void testParseTreeToRPN2() {
Node node = new Formula().parseFormula("(1+2)^2*(3+4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
assertEquals("4", rpn.get(0).getData());
assertEquals("3", rpn.get(1).getData());
assertEquals("+", rpn.get(2).getData());
assertEquals("2", rpn.get(3).getData());
assertEquals("2", rpn.get(4).getData());
assertEquals("1", rpn.get(5).getData());
assertEquals("+", rpn.get(6).getData());
assertEquals("^", rpn.get(7).getData());
assertEquals("*", rpn.get(8).getData());
}
@Test
public void testParseTreeToRPN3() {
Node node = new Formula().parseFormula("(1.1+2)^3*(4+5)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
assertEquals("5", rpn.get(0).getData());
assertEquals("4", rpn.get(1).getData());
assertEquals("+", rpn.get(2).getData());
assertEquals("3", rpn.get(3).getData());
assertEquals("2", rpn.get(4).getData());
assertEquals("1.1", rpn.get(5).getData());
assertEquals("+", rpn.get(6).getData());
assertEquals("^", rpn.get(7).getData());
assertEquals("*", rpn.get(8).getData());
}
@Test
public void testParseTreeToRPN4() {
Node node = new Formula().parseFormula("(1 + -2) ^ 3 * (4 + 5)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
assertEquals("5", rpn.get(0).getData());
assertEquals("4", rpn.get(1).getData());
assertEquals("+", rpn.get(2).getData());
assertEquals("3", rpn.get(3).getData());
assertEquals("2", rpn.get(4).getData());
assertEquals("-1", rpn.get(5).getData());
assertEquals("*", rpn.get(6).getData());
assertEquals("1", rpn.get(7).getData());
assertEquals("+", rpn.get(8).getData());
assertEquals("^", rpn.get(9).getData());
assertEquals("*", rpn.get(10).getData());
}
@Test
public void testCalculate1() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Node node = new Formula().parseFormula("(1+-2)*(3+4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
System.out.println("");
assertEquals(-7, new Formula().calculateRpnInteger(rpn));
}
@Test
public void testCalculate2() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Node node = new Formula().parseFormula("((1+2)*3)+4");
List<Node> rpn = new Formula().parseTreeToRpn(node);
assertEquals(13, new Formula().calculateRpnInteger(rpn));
}
@Test
public void testCalculate3() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Node node = new Formula().parseFormula("(1+-2)-(3+4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
System.out.println("");
assertEquals(-8, new Formula().calculateRpnInteger(rpn));
}
@Test
public void testCalculate4() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Node node = new Formula().parseFormula("1*-2-(3*-4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
System.out.println("");
assertEquals(10, new Formula().calculateRpnInteger(rpn));
}
}
FormulaTestTestError.java
package net.pandamaster.trpg.utils.formula;
import static org.junit.Assert.*;
import java.lang.reflect.InvocationTargetException;
import java.util.List;
import org.junit.Test;
import net.pandamaster.trpg.utils.Node;
public class FormulaTestTestError {
@Test(expected = IllegalArgumentException.class)
public void testParseFormula1() {
Node node = new Formula().parseFormula("1++2");
assertEquals("1", node.getLeft().getData());
assertEquals("+", node.getData());
assertEquals("2", node.getRight().getData());
}
@Test(expected = IllegalArgumentException.class)
public void testParseTreeToRPN1() {
Node node = new Formula().parseFormula("1++2");
List<Node> rpn = new Formula().parseTreeToRpn(node);
System.out.println(rpn.toString());
assertEquals("4", rpn.get(0));
assertEquals("3", rpn.get(1));
assertEquals("+", rpn.get(2));
assertEquals("2", rpn.get(3));
assertEquals("1", rpn.get(4));
assertEquals("+", rpn.get(5));
assertEquals("*", rpn.get(6));
}
@Test(expected = IllegalArgumentException.class)
public void testCalculate1() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Node node = new Formula().parseFormula("(1++2)*(3+4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
assertEquals(21, new Formula().calculateRpnInteger(rpn));
}
@Test(expected = IllegalArgumentException.class)
public void testCalculate2() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Node node = new Formula().parseFormula("1*-2--(3*-4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
System.out.println("");
assertEquals(10, new Formula().calculateRpnInteger(rpn));
}
@Test(expected = IllegalArgumentException.class)
public void testCalculate3() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Node node = new Formula().parseFormula("-(1+2)*(3+4)");
List<Node> rpn = new Formula().parseTreeToRpn(node);
assertEquals(21, new Formula().calculateRpnInteger(rpn));
}
}
https://artofproblemsolving.com/community/c163h141553_how_to_convert_infix_to_postfixreverse_polish_notation https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
Recommended Posts