diff options
author | Adrien Hopkins <adrien.p.hopkins@gmail.com> | 2019-03-22 17:00:58 -0400 |
---|---|---|
committer | Adrien Hopkins <adrien.p.hopkins@gmail.com> | 2019-03-22 17:00:58 -0400 |
commit | 943496888d18b031be19ba8e7348ec188dc8eb6b (patch) | |
tree | 03b440bf7d7789be5fd88b8ce3785f900804c773 /src/org/unitConverter/math | |
parent | ea940f2c5b6450231ff9ce61f4b6704babdb0d9e (diff) |
Made BaseUnit a subclass of LinearUnit and made an expression parser
Diffstat (limited to 'src/org/unitConverter/math')
-rw-r--r-- | src/org/unitConverter/math/DecimalComparison.java | 107 | ||||
-rw-r--r-- | src/org/unitConverter/math/ExpressionParser.java | 627 | ||||
-rw-r--r-- | src/org/unitConverter/math/package-info.java | 23 |
3 files changed, 757 insertions, 0 deletions
diff --git a/src/org/unitConverter/math/DecimalComparison.java b/src/org/unitConverter/math/DecimalComparison.java new file mode 100644 index 0000000..e6fb733 --- /dev/null +++ b/src/org/unitConverter/math/DecimalComparison.java @@ -0,0 +1,107 @@ +/** + * Copyright (C) 2019 Adrien Hopkins + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <https://www.gnu.org/licenses/>. + */ +package org.unitConverter.math; + +/** + * A class that contains methods to compare float and double values. + * + * @author Adrien Hopkins + * @since 2019-03-18 + */ +public final class DecimalComparison { + /** + * The value used for double comparison. If two double values are within this value multiplied by the larger value, + * they are considered equal. + * + * @since 2019-03-18 + */ + public static final double DOUBLE_EPSILON = 1.0e-15; + + /** + * The value used for float comparison. If two float values are within this value multiplied by the larger value, + * they are considered equal. + * + * @since 2019-03-18 + */ + public static final float FLOAT_EPSILON = 1.0e-6f; + + /** + * Tests for equality of double values using {@link #DOUBLE_EPSILON}. + * + * @param a + * first value to test + * @param b + * second value to test + * @return whether they are equal + * @since 2019-03-18 + */ + public static final boolean equals(final double a, final double b) { + return DecimalComparison.equals(a, b, DOUBLE_EPSILON); + } + + /** + * Tests for double equality using a custom epsilon value. + * + * @param a + * first value to test + * @param b + * second value to test + * @param epsilon + * allowed difference + * @return whether they are equal + * @since 2019-03-18 + */ + public static final boolean equals(final double a, final double b, final double epsilon) { + return Math.abs(a - b) <= epsilon * Math.max(Math.abs(a), Math.abs(b)); + } + + /** + * Tests for equality of float values using {@link #FLOAT_EPSILON}. + * + * @param a + * first value to test + * @param b + * second value to test + * @return whether they are equal + * @since 2019-03-18 + */ + public static final boolean equals(final float a, final float b) { + return DecimalComparison.equals(a, b, FLOAT_EPSILON); + } + + /** + * Tests for float equality using a custom epsilon value. + * + * @param a + * first value to test + * @param b + * second value to test + * @param epsilon + * allowed difference + * @return whether they are equal + * @since 2019-03-18 + */ + public static final boolean equals(final float a, final float b, final float epsilon) { + return Math.abs(a - b) <= epsilon * Math.max(Math.abs(a), Math.abs(b)); + } + + // You may NOT get any DecimalComparison instances + private DecimalComparison() { + throw new AssertionError(); + } + +} diff --git a/src/org/unitConverter/math/ExpressionParser.java b/src/org/unitConverter/math/ExpressionParser.java new file mode 100644 index 0000000..e06a58b --- /dev/null +++ b/src/org/unitConverter/math/ExpressionParser.java @@ -0,0 +1,627 @@ +/** + * Copyright (C) 2019 Adrien Hopkins + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <https://www.gnu.org/licenses/>. + */ +package org.unitConverter.math; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Deque; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.function.BinaryOperator; +import java.util.function.Function; +import java.util.function.UnaryOperator; + +/** + * An object that can parse expressions with unary or binary operators. + * + * @author Adrien Hopkins + * @param <T> + * type of object that exists in parsed expressions + * @since 2019-03-14 + */ +// TODO: possibly make this class non-final? +public final class ExpressionParser<T> { + /** + * A builder that can create {@code ExpressionParser<T>} instances. + * + * @author Adrien Hopkins + * @param <T> + * type of object that exists in parsed expressions + * @since 2019-03-17 + */ + public static final class Builder<T> { + /** + * A function that obtains a parseable object from a string. For example, an integer {@code ExpressionParser} + * would use {@code Integer::parseInt}. + * + * @since 2019-03-14 + */ + private final Function<String, T> objectObtainer; + + /** + * A map mapping operator strings to operator functions, for unary operators. + * + * @since 2019-03-14 + */ + private final Map<String, PriorityUnaryOperator<T>> unaryOperators; + + /** + * A map mapping operator strings to operator functions, for binary operators. + * + * @since 2019-03-14 + */ + private final Map<String, PriorityBinaryOperator<T>> binaryOperators; + + /** + * Creates the {@code Builder}. + * + * @param objectObtainer + * a function that can turn strings into objects of the type handled by the parser. + * @throws NullPointerException + * if {@code objectObtainer} is null + * @since 2019-03-17 + */ + public Builder(final Function<String, T> objectObtainer) { + this.objectObtainer = Objects.requireNonNull(objectObtainer, "objectObtainer must not be null."); + this.unaryOperators = new HashMap<>(); + this.binaryOperators = new HashMap<>(); + } + + /** + * Adds a binary operator to the builder. + * + * @param text + * text used to reference the operator, like '+' + * @param operator + * operator to add + * @param priority + * operator's priority, which determines which operators are applied first + * @return this builder + * @throws NullPointerException + * if {@code text} or {@code operator} is null + * @since 2019-03-17 + */ + public Builder<T> addBinaryOperator(final String text, final BinaryOperator<T> operator, final int priority) { + Objects.requireNonNull(text, "text must not be null."); + Objects.requireNonNull(operator, "operator must not be null."); + + // Unfortunately, I cannot use a lambda because the PriorityBinaryOperator requires arguments. + final PriorityBinaryOperator<T> priorityOperator = new PriorityBinaryOperator<T>(priority) { + @Override + public T apply(final T t, final T u) { + return operator.apply(t, u); + } + + }; + this.binaryOperators.put(text, priorityOperator); + return this; + } + + /** + * Adds a unary operator to the builder. + * + * @param text + * text used to reference the operator, like '-' + * @param operator + * operator to add + * @param priority + * operator's priority, which determines which operators are applied first + * @return this builder + * @throws NullPointerException + * if {@code text} or {@code operator} is null + * @since 2019-03-17 + */ + public Builder<T> addUnaryOperator(final String text, final UnaryOperator<T> operator, final int priority) { + Objects.requireNonNull(text, "text must not be null."); + Objects.requireNonNull(operator, "operator must not be null."); + + // Unfortunately, I cannot use a lambda because the PriorityUnaryOperator requires arguments. + final PriorityUnaryOperator<T> priorityOperator = new PriorityUnaryOperator<T>(priority) { + @Override + public T apply(final T t) { + return operator.apply(t); + } + }; + this.unaryOperators.put(text, priorityOperator); + return this; + } + + /** + * @return an {@code ExpressionParser<T>} instance with the properties given to this builder + * @since 2019-03-17 + */ + public ExpressionParser<T> build() { + return new ExpressionParser<>(this.objectObtainer, this.unaryOperators, this.binaryOperators); + } + } + + /** + * A binary operator with a priority field that determines which operators apply first. + * + * @author Adrien Hopkins + * @param <T> + * type of operand and result + * @since 2019-03-17 + */ + private static abstract class PriorityBinaryOperator<T> + implements BinaryOperator<T>, Comparable<PriorityBinaryOperator<T>> { + /** + * The operator's priority. Higher-priority operators are applied before lower-priority operators + */ + private final int priority; + + /** + * Creates the {@code PriorityBinaryOperator}. + * + * @param priority + * operator's priority + * @since 2019-03-17 + */ + public PriorityBinaryOperator(final int priority) { + this.priority = priority; + } + + /** + * Compares this object to another by priority. + * + * <p> + * {@inheritDoc} + */ + @Override + public int compareTo(final PriorityBinaryOperator<T> o) { + if (this.priority < o.priority) + return -1; + else if (this.priority > o.priority) + return 1; + else + return 0; + } + + /** + * @return priority + * @since 2019-03-22 + */ + public final int getPriority() { + return this.priority; + } + } + + /** + * A unary operator with a priority field that determines which operators apply first. + * + * @author Adrien Hopkins + * @param <T> + * type of operand and result + * @since 2019-03-17 + */ + private static abstract class PriorityUnaryOperator<T> + implements UnaryOperator<T>, Comparable<PriorityUnaryOperator<T>> { + /** + * The operator's priority. Higher-priority operators are applied before lower-priority operators + */ + private final int priority; + + /** + * Creates the {@code PriorityUnaryOperator}. + * + * @param priority + * operator's priority + * @since 2019-03-17 + */ + public PriorityUnaryOperator(final int priority) { + this.priority = priority; + } + + /** + * Compares this object to another by priority. + * + * <p> + * {@inheritDoc} + */ + @Override + public int compareTo(final PriorityUnaryOperator<T> o) { + if (this.priority < o.priority) + return -1; + else if (this.priority > o.priority) + return 1; + else + return 0; + } + + /** + * @return priority + * @since 2019-03-22 + */ + public final int getPriority() { + return this.priority; + } + } + + /** + * The types of tokens that are available. + * + * @author Adrien Hopkins + * @since 2019-03-14 + */ + private static enum TokenType { + OBJECT, UNARY_OPERATOR, BINARY_OPERATOR; + } + + /** + * The opening bracket. + * + * @since 2019-03-22 + */ + public static final char OPENING_BRACKET = '('; + + /** + * The closing bracket. + * + * @since 2019-03-22 + */ + public static final char CLOSING_BRACKET = ')'; + + /** + * Finds the other bracket in a pair of brackets, given the position of one. + * + * @param string + * string that contains brackets + * @param bracketPosition + * position of first bracket + * @return position of matching bracket + * @throws NullPointerException + * if string is null + * @since 2019-03-22 + */ + private static int findBracketPair(final String string, final int bracketPosition) { + Objects.requireNonNull(string, "string must not be null."); + + final char openingBracket = string.charAt(bracketPosition); + + // figure out what closing bracket to look for + final char closingBracket; + switch (openingBracket) { + case '(': + closingBracket = ')'; + break; + case '[': + closingBracket = ']'; + break; + case '{': + closingBracket = '}'; + break; + default: + throw new IllegalArgumentException(String.format("Invalid bracket '%s'", openingBracket)); + } + + // level of brackets. every opening bracket increments this; every closing bracket decrements it + int bracketLevel = 0; + + // iterate over the string to find the closing bracket + for (int currentPosition = bracketPosition; currentPosition < string.length(); currentPosition++) { + final char currentCharacter = string.charAt(currentPosition); + + if (currentCharacter == openingBracket) { + bracketLevel++; + } else if (currentCharacter == closingBracket) { + bracketLevel--; + if (bracketLevel == 0) + return currentPosition; + } + } + + throw new IllegalArgumentException("No matching bracket found."); + } + + public static void main(final String[] args) { + final ExpressionParser<Integer> numberParser = new ExpressionParser.Builder<>(Integer::parseInt) + .addBinaryOperator("+", (o1, o2) -> o1 + o2, 0).addBinaryOperator("*", (o1, o2) -> o1 * o2, 1) + .addBinaryOperator("^", (o1, o2) -> (int) Math.pow(o1, o2), 2).build(); + System.out.println(numberParser.convertExpressionToReversePolish("(1 + 2) ^ 5 * 3")); + System.out.println(numberParser.parseExpression("(1 + 2) ^ 5 * 3")); // 729 + } + + /** + * Swaps two elements in a list. Modifies the list passed in instead of returning a modified list. + * + * @param list + * list to swap elements + * @param firstIndex + * index of first element to swap + * @param otherIndex + * index of other element to swap + * @throws NullPointerException + * if list is null + * @since 2019-03-20 + */ + private static <E> void swap(final List<E> list, final int firstIndex, final int otherIndex) { + Objects.requireNonNull(list, "list must not be null."); + final E temp = list.get(firstIndex); + list.set(firstIndex, list.get(otherIndex)); + list.set(otherIndex, temp); + } + + /** + * A function that obtains a parseable object from a string. For example, an integer {@code ExpressionParser} would + * use {@code Integer::parseInt}. + * + * @since 2019-03-14 + */ + private final Function<String, T> objectObtainer; + + /** + * A map mapping operator strings to operator functions, for unary operators. + * + * @since 2019-03-14 + */ + private final Map<String, PriorityUnaryOperator<T>> unaryOperators; + + /** + * A map mapping operator strings to operator functions, for binary operators. + * + * @since 2019-03-14 + */ + private final Map<String, PriorityBinaryOperator<T>> binaryOperators; + + /** + * Creates the {@code ExpressionParser}. + * + * @param objectObtainer + * function to get objects from strings + * @param unaryOperators + * operators available to the parser + * @since 2019-03-14 + */ + private ExpressionParser(final Function<String, T> objectObtainer, + final Map<String, PriorityUnaryOperator<T>> unaryOperators, + final Map<String, PriorityBinaryOperator<T>> binaryOperators) { + this.objectObtainer = objectObtainer; + this.unaryOperators = unaryOperators; + this.binaryOperators = binaryOperators; + } + + /** + * Converts a given mathematical expression to reverse Polish notation (operators after operands). + * <p> + * For example,<br> + * {@code 2 * (3 + 4)}<br> + * becomes<br> + * {@code 2 3 4 + *}. + * + * @param expression + * expression + * @return expression in RPN + * @since 2019-03-17 + */ + private String convertExpressionToReversePolish(final String expression) { + Objects.requireNonNull(expression, "expression must not be null."); + + final List<String> components = new ArrayList<>(); + + // the part of the expression remaining to parse + String partialExpression = expression; + + // find and deal with brackets + while (partialExpression.indexOf(OPENING_BRACKET) != -1) { + final int openingBracketPosition = partialExpression.indexOf(OPENING_BRACKET); + final int closingBracketPosition = findBracketPair(partialExpression, openingBracketPosition); + components.addAll(Arrays.asList(partialExpression.substring(0, openingBracketPosition).split(" "))); + components.add(this.convertExpressionToReversePolish( + partialExpression.substring(openingBracketPosition + 1, closingBracketPosition))); + partialExpression = partialExpression.substring(closingBracketPosition + 1); + } + + // add everything else + components.addAll(Arrays.asList(partialExpression.split(" "))); + + // remove empty entries + while (components.contains("")) { + components.remove(""); + } + + // turn the expression into reverse Polish + while (true) { + final int highestPriorityOperatorPosition = this.findHighestPriorityOperatorPosition(components); + if (highestPriorityOperatorPosition == -1) { + break; + } + + switch (this.getTokenType(components.get(highestPriorityOperatorPosition))) { + case UNARY_OPERATOR: + final String unaryOperator = components.remove(highestPriorityOperatorPosition); + final String operand = components.remove(highestPriorityOperatorPosition); + components.add(highestPriorityOperatorPosition, operand + " " + unaryOperator); + break; + case BINARY_OPERATOR: + final String binaryOperator = components.remove(highestPriorityOperatorPosition); + final String operand1 = components.remove(highestPriorityOperatorPosition - 1); + final String operand2 = components.remove(highestPriorityOperatorPosition - 1); + components.add(highestPriorityOperatorPosition - 1, + operand2 + " " + operand1 + " " + binaryOperator); + break; + default: + throw new AssertionError("Expected operator, found non-operator."); + } + } + + // join all of the components together, then ensure there is only one space in a row + String expressionRPN = String.join(" ", components).replaceAll(" +", " "); + + while (expressionRPN.charAt(0) == ' ') { + expressionRPN = expressionRPN.substring(1); + } + while (expressionRPN.charAt(expressionRPN.length() - 1) == ' ') { + expressionRPN = expressionRPN.substring(0, expressionRPN.length() - 1); + } + return expressionRPN; + + // TODO method stub org.unitConverter.expressionParser.ExpressionParser.convertExpressionToPolish(expression) + } + + /** + * Finds the position of the highest-priority operator in a list + * + * @param components + * components to test + * @param blacklist + * positions of operators that should be ignored + * @return position of highest priority, or -1 if the list contains no operators + * @throws NullPointerException + * if components is null + * @since 2019-03-22 + */ + private int findHighestPriorityOperatorPosition(final List<String> components) { + Objects.requireNonNull(components, "components must not be null."); + // find highest priority + int maxPriority = Integer.MIN_VALUE; + int maxPriorityPosition = -1; + + // go over components one by one + // if it is an operator, test its priority to see if it's max + // if it is, update maxPriority and maxPriorityPosition + for (int i = 0; i < components.size(); i++) { + + switch (this.getTokenType(components.get(i))) { + case UNARY_OPERATOR: + final PriorityUnaryOperator<T> unaryOperator = this.unaryOperators.get(components.get(i)); + final int unaryPriority = unaryOperator.getPriority(); + + if (unaryPriority > maxPriority) { + maxPriority = unaryPriority; + maxPriorityPosition = i; + } + break; + case BINARY_OPERATOR: + final PriorityBinaryOperator<T> binaryOperator = this.binaryOperators.get(components.get(i)); + final int binaryPriority = binaryOperator.getPriority(); + + if (binaryPriority > maxPriority) { + maxPriority = binaryPriority; + maxPriorityPosition = i; + } + break; + default: + break; + } + } + + // max priority position found + return maxPriorityPosition; + } + + /** + * Determines whether an inputted string is an object or an operator + * + * @param token + * string to input + * @return type of token it is + * @throws NullPointerException + * if {@code expression} is null + * @since 2019-03-14 + */ + private TokenType getTokenType(final String token) { + Objects.requireNonNull(token, "token must not be null."); + + if (this.unaryOperators.containsKey(token)) + return TokenType.UNARY_OPERATOR; + else if (this.binaryOperators.containsKey(token)) + return TokenType.BINARY_OPERATOR; + else + return TokenType.OBJECT; + } + + /** + * Parses an expression. + * + * @param expression + * expression to parse + * @return result + * @throws NullPointerException + * if {@code expression} is null + * @since 2019-03-14 + */ + public T parseExpression(final String expression) { + return this.parseReversePolishExpression(this.convertExpressionToReversePolish(expression)); + } + + /** + * Parses an expression expressed in reverse Polish notation. + * + * @param expression + * expression to parse + * @return result + * @throws NullPointerException + * if {@code expression} is null + * @since 2019-03-14 + */ + private T parseReversePolishExpression(final String expression) { + Objects.requireNonNull(expression, "expression must not be null."); + + final Deque<T> stack = new ArrayDeque<>(); + + // iterate over every item in the expression, then + for (final String item : expression.split(" ")) { + // choose a path based on what kind of thing was just read + switch (this.getTokenType(item)) { + + case BINARY_OPERATOR: + if (stack.size() < 2) + throw new IllegalStateException(String.format( + "Attempted to call binary operator %s with only %d arguments.", item, stack.size())); + + // get two arguments and operator, then apply! + final T o1 = stack.pop(); + final T o2 = stack.pop(); + final BinaryOperator<T> binaryOperator = this.binaryOperators.get(item); + + stack.push(binaryOperator.apply(o1, o2)); + break; + + case OBJECT: + // just add it to the stack + stack.push(this.objectObtainer.apply(item)); + break; + + case UNARY_OPERATOR: + if (stack.size() < 1) + throw new IllegalStateException(String.format( + "Attempted to call unary operator %s with only %d arguments.", item, stack.size())); + + // get one argument and operator, then apply! + final T o = stack.pop(); + final UnaryOperator<T> unaryOperator = this.unaryOperators.get(item); + + stack.push(unaryOperator.apply(o)); + break; + default: + throw new AssertionError( + String.format("Internal error: Invalid token type %s.", this.getTokenType(item))); + + } + } + + // return answer, or throw an exception if I can't + if (stack.size() > 1) + throw new IllegalStateException("Computation ended up with more than one answer."); + else if (stack.size() == 0) + throw new IllegalStateException("Computation ended up without an answer."); + return stack.pop(); + } +} diff --git a/src/org/unitConverter/math/package-info.java b/src/org/unitConverter/math/package-info.java new file mode 100644 index 0000000..65d6b23 --- /dev/null +++ b/src/org/unitConverter/math/package-info.java @@ -0,0 +1,23 @@ +/** + * Copyright (C) 2019 Adrien Hopkins + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <https://www.gnu.org/licenses/>. + */ +/** + * A module that is capable of parsing expressions of things, like mathematical expressions or unit expressions. + * + * @author Adrien Hopkins + * @since 2019-03-14 + */ +package org.unitConverter.math;
\ No newline at end of file |