・ Parce qu'il s'agit d'un algorithme oléore, le raisonnement peut être étrange en premier ・ Petite explication (lire la source et les commentaires) ・ Bienvenue en plongée
Dans le service que je fais maintenant, il y a un écran pour que l'utilisateur entre la formule de calcul, il était donc nécessaire de convertir la notation d'indentation en notation polonaise inverse, de l'enregistrer et de la calculer.
Java 1.8 Spring 4.x
Créez une classe Node à utiliser dans les arborescences de syntaxe et les tableaux.
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;
}
}
Une classe qui représente un nœud d'un arbre dichotomisé. Il a une référence au nœud à la fin des branches gauche et droite et au nœud parent.
Analysez la notation neutre, générez l'arbre de syntaxe et convertissez-la en notation polonaise inverse. C'est un code qui a été créé après essais et erreurs, donc c'est assez approximatif. Je ne connais pas la théorie des graphes.
Formula.java
public class Formula {
//Constante de chaîne d'expression régulière
//espace
public static final String REGEXP_FORMAT = "(%s)";
public static final String WHITE_SPACE = "\\s";
//Entiers, variables, nombre de points décimaux (les variables n'ont pas encore été prises en compte)
public static final String OPERANDS = "\\d\\.\\d|\\d|\\w";
//Une liste d'opérateurs
public static final String OPERATORS = "\\+|\\-|\\*|\\/|%|\\^";
//supports
public static final String BRACKETS = "\\(|\\)";
//Support ouvert
public static final String OPENING_BRACKET = "\\(";
//Support de fermeture
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))*)$";
//Coefficient de calcul des valeurs négatives
public static final String COEFFICIENT = "-1";
public static final String MULTIPLY = "*";
//Obtient pour augmenter la priorité d'opérateur entre parenthèses
public static final int INFLATE_NUMBER = 10;
//Formule saisie par l'utilisateur
private String formula;
//La racine de l'arbre de syntaxe
private Node tree;
//Arrangement de la notation polonaise inversée
private List<Node> rpn;
//Carte de priorité pour chaque opérateur et opérande
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));
//File d'attente pour stocker les opérateurs et les opérandes en notation neutre
private Deque<Node> queue = new ArrayDeque<>();
//constructeur
public Formula() {
}
public Formula(String formula) {
this.formula = formula;
}
public Node parseFormula() throws IllegalArgumentException {
return parseFormula(formula);
}
//Convertir la notation neutre en notation polonaise inversée
public Node parseFormula(String formula) throws IllegalArgumentException {
//Supprimer l'espace supplémentaire
String trim = formula.replaceAll(getRegExp(WHITE_SPACE), "");
//S'il contient des caractères supplémentaires
String temp = trim.replaceAll(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");
Assert.isTrue(temp.length() == 0, "");
int bracket = 0;
//Décomposer une formule de chaîne en opérateurs et opérandes
while(trim.length() > 0) {
//Extraire le premier opérateur ou opérande
String flagment = getFlagment(trim);
//Effacer la partie supprimée
trim = trim.replaceFirst(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");
//Extraire le ValidCharacter correspondant de la carte de priorité
ValidCharacter vc = VALID_CHARACTERS_MAP.entrySet().stream().filter(
entry -> {
return flagment.matches(entry.getKey());
}
).findFirst().get().getValue();
Assert.isTrue(vc != null, "");
//Pour les crochets ouverts, augmentez la priorité
if(flagment.matches(OPENING_BRACKET)) {
bracket++;
continue;
}
//Diminuer la priorité pour fermer les crochets
else if(flagment.matches(CLOSING_BRACKET)) {
bracket--;
continue;
}
String test_flagment = getFlagment(trim);
//Si une valeur négative est incluse-Remplacer par multiplication par 1
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)));
}
//S'il s'agit d'une valeur positive, stockez-la dans la file d'attente telle quelle
else {
queue.add(new Node(flagment, flagment.matches(getRegExp(OPERANDS))?vc.getPrecedence():(vc.getPrecedence() + INFLATE_NUMBER * bracket)));
}
}
//Vérifiez si la formule commence par un opérande et se termine par un opérateur entre
Assert.isTrue(String.join("", queue.stream().map(node -> node.getData()).collect(Collectors.toList())).matches(VALID_FORMULA), "");
//Faire du premier élément de la file d'attente la racine de l'arbre de syntaxe
Node currentNode = queue.pollFirst();
//Générer une arborescence de syntaxe
currentNode.setLeft(new Node("", Integer.MAX_VALUE));
currentNode.setRight(new Node("", Integer.MAX_VALUE));
do {
//Extraire le début de la file d'attente
Node poll = queue.pollFirst();
Assert.isTrue(bracket > 0 || !")".equals(poll.getData()), "");
Node left = currentNode, right = null;
//Recherchez jusqu'à ce que vous trouviez un nœud avec une priorité plus élevée que le nœud extrait
do {
//Lorsqu'un nœud de haute priorité est trouvé
if(currentNode.getPrecede() >= poll.getPrecede()) {
left = currentNode;
right = new Node("", Integer.MAX_VALUE);
if(currentNode.getParent() != null) {
currentNode.getParent().setRight(poll);
}
currentNode = poll;
break;
}
//Pour les nœuds de faible priorité, descendez un à droite de la branche
else if(currentNode.getPrecede() < poll.getPrecede()) {
currentNode = currentNode.getRight();
}
}while(true);
//Insérer un nœud dans l'arborescence
currentNode.setLeft(left);
currentNode.setRight(right);
currentNode = currentNode.searchTop();
}while(!queue.isEmpty());
setTree(currentNode.searchTop());
return getTree();
}
//Extraire le début de la formule de la chaîne de caractères
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);
}
//Convertir l'arbre de syntaxe en tableau en notation polonaise inverse
public List<Node> parseTreeToRpn(Node tree) {
//Enfin retourner
rpn = new ArrayList<>();
Stack<Node> stack = new Stack<>();
stack.push(tree);
while(!stack.isEmpty() ) {
//Stockez les nœuds de la pile dans un tableau
Node node = stack.pop();
rpn.add(node);
//Le nœud feuille est un entier.MAX_Puisqu'il s'agit d'une VALEUR, les branches gauche et droite du nœud de priorité inférieure sont stockées dans la pile.
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);
}
//Calculer la formule de la notation polonaise inverse
public int calculateRpnInteger(List<Node> rpn) throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Stack<Node> stack = new Stack<>();
Calculator calc = new Calculator();
//Boucle pour tous les éléments du tableau
for(Node token : rpn) {
//S'il s'agit d'un opérande, il est chargé sur la pile.
if(token.getPrecede() == Integer.MAX_VALUE - 1) {
stack.push(token);
}
//Pour l'opérateur, prenez la valeur binaire de la pile et calculez
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));
}
}
//Renvoie le résultat du calcul
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;
}
}
//Classe interne qui représente la priorité des opérateurs et des opérandes
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;
}
}
La séquence de notation polonaise inverse est retirée du début et calculée séquentiellement.
Calculator.java
public class Calculator {
private String key;
private Map<String, Method> calculators = new HashMap<>();
//Stockez la méthode de calcul pour chaque opérateur dans la carte de hachage.
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}));
}
//Effectuez le calcul en passant l'opérateur et deux opérandes.
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);
}
//une addition
public Object addInteger(String left, String right) {
return Integer.parseInt(left) + Integer.parseInt(right);
}
//soustraction
public Object subtractInteger(String left, String right) {
return Integer.parseInt(left) - Integer.parseInt(right);
}
//multiplication
public Object multiplyInteger(String left, String right) {
return Integer.parseInt(left) * Integer.parseInt(right);
}
//division
public Object divideInteger(String left, String right) {
return Integer.parseInt(left) / Integer.parseInt(right);
}
//Surplus
public Object surplusInteger(String left, String right) {
return Integer.parseInt(left) % Integer.parseInt(right);
}
//Puissance
public Object powerFloat(String left, String right) {
return (int)Math.pow(Double.parseDouble(left), Double.parseDouble(right));
}
}
C'est une classe qui calcule simplement, donc aucune explication n'est requise.
Appliquez quelques formules et testez si cela fonctionne comme prévu. Faites-moi savoir s'il existe des cas de test qui ne fonctionnent pas.
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