・ Because it is an oleore algorithm, the reasoning may be strange in the first place ・ Small explanation (read the source and comments) ・ Plunge welcome
In the service I'm making now, there is a screen for the user to enter a calculation formula, so it was necessary to convert the infix notation to reverse Polish notation, save it, and calculate it.
Java 1.8 Spring 4.x
Create a Node class for use in syntax trees and 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;
}
}
A class that represents one node of a binary tree. It has a reference to the node at the end of the left and right branches and the parent node.
Analyze infix notation, generate syntax tree, and convert to reverse Polish notation. The code was created after trial and error, so it's quite rough. I don't know the theory of graphs.
Formula.java
public class Formula {
//Regular expression string constant
//space
public static final String REGEXP_FORMAT = "(%s)";
public static final String WHITE_SPACE = "\\s";
//Integers, variables, decimal numbers (variables have not been considered yet)
public static final String OPERANDS = "\\d\\.\\d|\\d|\\w";
//A list of operators
public static final String OPERATORS = "\\+|\\-|\\*|\\/|%|\\^";
//brackets
public static final String BRACKETS = "\\(|\\)";
//Open brackets
public static final String OPENING_BRACKET = "\\(";
//Closing bracket
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 for calculating negative values
public static final String COEFFICIENT = "-1";
public static final String MULTIPLY = "*";
//Geta to raise operator priority in parentheses
public static final int INFLATE_NUMBER = 10;
//Formulas entered by the user
private String formula;
//Syntax tree root
private Node tree;
//Array of reverse Polish notation
private List<Node> rpn;
//Priority map for each operator and operand
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));
//Queue to store operators and operands in infix notation
private Deque<Node> queue = new ArrayDeque<>();
//constructor
public Formula() {
}
public Formula(String formula) {
this.formula = formula;
}
public Node parseFormula() throws IllegalArgumentException {
return parseFormula(formula);
}
//Convert infix notation to reverse Polish notation
public Node parseFormula(String formula) throws IllegalArgumentException {
//Remove extra space
String trim = formula.replaceAll(getRegExp(WHITE_SPACE), "");
//Whether it contains extra characters
String temp = trim.replaceAll(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");
Assert.isTrue(temp.length() == 0, "");
int bracket = 0;
//Decompose string formulas into operators and operands
while(trim.length() > 0) {
//Fetch the first operator or operand
String flagment = getFlagment(trim);
//Erase the removed part
trim = trim.replaceFirst(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");
//Extract the matching ValidCharacter from the priority map
ValidCharacter vc = VALID_CHARACTERS_MAP.entrySet().stream().filter(
entry -> {
return flagment.matches(entry.getKey());
}
).findFirst().get().getValue();
Assert.isTrue(vc != null, "");
//Increase priority for open brackets
if(flagment.matches(OPENING_BRACKET)) {
bracket++;
continue;
}
//Decrease priority for closing brace
else if(flagment.matches(CLOSING_BRACKET)) {
bracket--;
continue;
}
String test_flagment = getFlagment(trim);
//If a negative value is included-Replace with multiplication with 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)));
}
//If it is a positive value, it is stored in the queue as it is
else {
queue.add(new Node(flagment, flagment.matches(getRegExp(OPERANDS))?vc.getPrecedence():(vc.getPrecedence() + INFLATE_NUMBER * bracket)));
}
}
//Check if the formula starts with an operand and ends with an operator in between
Assert.isTrue(String.join("", queue.stream().map(node -> node.getData()).collect(Collectors.toList())).matches(VALID_FORMULA), "");
//Make the first element of the queue the root of the syntax tree
Node currentNode = queue.pollFirst();
//Syntax tree generation
currentNode.setLeft(new Node("", Integer.MAX_VALUE));
currentNode.setRight(new Node("", Integer.MAX_VALUE));
do {
//Extract the beginning of the queue
Node poll = queue.pollFirst();
Assert.isTrue(bracket > 0 || !")".equals(poll.getData()), "");
Node left = currentNode, right = null;
//Search until a node with a higher priority than the extracted node is found
do {
//If a high priority node is found
if(currentNode.getPrecede() >= poll.getPrecede()) {
left = currentNode;
right = new Node("", Integer.MAX_VALUE);
if(currentNode.getParent() != null) {
currentNode.getParent().setRight(poll);
}
currentNode = poll;
break;
}
//For low priority nodes, go down one to the right of the branch
else if(currentNode.getPrecede() < poll.getPrecede()) {
currentNode = currentNode.getRight();
}
}while(true);
//Insert node into tree
currentNode.setLeft(left);
currentNode.setRight(right);
currentNode = currentNode.searchTop();
}while(!queue.isEmpty());
setTree(currentNode.searchTop());
return getTree();
}
//Extract the beginning from the formula of the string
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);
}
//Convert syntax tree to array in reverse Polish notation
public List<Node> parseTreeToRpn(Node tree) {
//Finally flip
rpn = new ArrayList<>();
Stack<Node> stack = new Stack<>();
stack.push(tree);
while(!stack.isEmpty() ) {
//Store the nodes on the stack in an array
Node node = stack.pop();
rpn.add(node);
//Leaf node is Integer.MAX_Since it is a VALUE, the left and right branches of the node with a lower priority are stored on the stack.
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);
}
//Calculate the formula for reverse Polish notation
public int calculateRpnInteger(List<Node> rpn) throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
Stack<Node> stack = new Stack<>();
Calculator calc = new Calculator();
//Loop for all elements of the array
for(Node token : rpn) {
//If it is an operand, put it on the stack
if(token.getPrecede() == Integer.MAX_VALUE - 1) {
stack.push(token);
}
//For the operator, take the binary value from the stack and calculate
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));
}
}
//Returns the calculation result
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;
}
}
//Inner class that represents the priority of operators and operands
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;
}
}
The array in reverse Polish notation is taken out from the beginning and calculated sequentially.
Calculator.java
public class Calculator {
private String key;
private Map<String, Method> calculators = new HashMap<>();
//Store the calculation method for each operator in the 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}));
}
//Perform the calculation, passing the operator and two operands.
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);
}
//addition
public Object addInteger(String left, String right) {
return Integer.parseInt(left) + Integer.parseInt(right);
}
//subtraction
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);
}
//Exponentiation
public Object powerFloat(String left, String right) {
return (int)Math.pow(Double.parseDouble(left), Double.parseDouble(right));
}
}
This is a class that simply calculates, so no explanation is needed.
Apply some formulas and test if it works as expected. Let me know if there are any test cases that don't work.
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