diff options
Diffstat (limited to 'src/org/unitConverter/math/ExpressionParser.java')
| -rw-r--r-- | src/org/unitConverter/math/ExpressionParser.java | 708 |
1 files changed, 0 insertions, 708 deletions
diff --git a/src/org/unitConverter/math/ExpressionParser.java b/src/org/unitConverter/math/ExpressionParser.java deleted file mode 100644 index 8a0e97d..0000000 --- a/src/org/unitConverter/math/ExpressionParser.java +++ /dev/null @@ -1,708 +0,0 @@ -/** - * 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 - * @since v0.2.0 - */ -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 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - private final Function<String, ? extends T> objectObtainer; - - /** - * The function of the space as an operator (like 3 x y) - * - * @since 2019-03-22 - * @since v0.2.0 - */ - private String spaceFunction = null; - - /** - * A map mapping operator strings to operator functions, for unary operators. - * - * @since 2019-03-14 - * @since v0.2.0 - */ - private final Map<String, PriorityUnaryOperator<T>> unaryOperators; - - /** - * A map mapping operator strings to operator functions, for binary operators. - * - * @since 2019-03-14 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - public Builder(final Function<String, ? extends 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 - * @since v0.2.0 - */ - 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 function for spaces. You must use the text of an existing binary operator. - * - * @param operator - * text of operator to use - * @return this builder - * @since 2019-03-22 - * @since v0.2.0 - */ - public Builder<T> addSpaceFunction(final String operator) { - Objects.requireNonNull(operator, "operator must not be null."); - - if (!this.binaryOperators.containsKey(operator)) - throw new IllegalArgumentException(String.format("Could not find binary operator '%s'", operator)); - - this.spaceFunction = operator; - 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 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - public ExpressionParser<T> build() { - return new ExpressionParser<>(this.objectObtainer, this.unaryOperators, this.binaryOperators, - this.spaceFunction); - } - } - - /** - * 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 - * @since v0.2.0 - */ - 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 - * - * @since 2019-03-17 - * @since v0.2.0 - */ - private final int priority; - - /** - * Creates the {@code PriorityBinaryOperator}. - * - * @param priority - * operator's priority - * @since 2019-03-17 - * @since v0.2.0 - */ - public PriorityBinaryOperator(final int priority) { - this.priority = priority; - } - - /** - * Compares this object to another by priority. - * - * <p> - * {@inheritDoc} - * </p> - * - * @since 2019-03-17 - * @since v0.2.0 - */ - @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 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - 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 - * - * @since 2019-03-17 - * @since v0.2.0 - */ - private final int priority; - - /** - * Creates the {@code PriorityUnaryOperator}. - * - * @param priority - * operator's priority - * @since 2019-03-17 - * @since v0.2.0 - */ - public PriorityUnaryOperator(final int priority) { - this.priority = priority; - } - - /** - * Compares this object to another by priority. - * - * <p> - * {@inheritDoc} - * </p> - * - * @since 2019-03-17 - * @since v0.2.0 - */ - @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 - * @since v0.2.0 - */ - public final int getPriority() { - return this.priority; - } - } - - /** - * The types of tokens that are available. - * - * @author Adrien Hopkins - * @since 2019-03-14 - * @since v0.2.0 - */ - private static enum TokenType { - OBJECT, UNARY_OPERATOR, BINARY_OPERATOR; - } - - /** - * The opening bracket. - * - * @since 2019-03-22 - * @since v0.2.0 - */ - public static final char OPENING_BRACKET = '('; - - /** - * The closing bracket. - * - * @since 2019-03-22 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - 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."); - } - - /** - * 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 - * @since v0.2.0 - */ - private final Function<String, ? extends T> objectObtainer; - - /** - * A map mapping operator strings to operator functions, for unary operators. - * - * @since 2019-03-14 - * @since v0.2.0 - */ - private final Map<String, PriorityUnaryOperator<T>> unaryOperators; - - /** - * A map mapping operator strings to operator functions, for binary operators. - * - * @since 2019-03-14 - * @since v0.2.0 - */ - private final Map<String, PriorityBinaryOperator<T>> binaryOperators; - - /** - * The operator for space, or null if spaces have no function. - * - * @since 2019-03-22 - * @since v0.2.0 - */ - private final String spaceOperator; - - /** - * Creates the {@code ExpressionParser}. - * - * @param objectObtainer - * function to get objects from strings - * @param unaryOperators - * unary operators available to the parser - * @param binaryOperators - * binary operators available to the parser - * @param spaceOperator - * operator used by spaces - * @since 2019-03-14 - * @since v0.2.0 - */ - private ExpressionParser(final Function<String, ? extends T> objectObtainer, - final Map<String, PriorityUnaryOperator<T>> unaryOperators, - final Map<String, PriorityBinaryOperator<T>> binaryOperators, final String spaceOperator) { - this.objectObtainer = objectObtainer; - this.unaryOperators = unaryOperators; - this.binaryOperators = binaryOperators; - this.spaceOperator = spaceOperator; - } - - /** - * 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 - * @since v0.2.0 - */ - 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); - - // check for function - if (openingBracketPosition > 0 && partialExpression.charAt(openingBracketPosition - 1) != ' ') { - // function like sin(2) or tempF(32) - // find the position of the last space - int spacePosition = openingBracketPosition; - while (spacePosition >= 0 && partialExpression.charAt(spacePosition) != ' ') { - spacePosition--; - } - // then split the function into pre-function and function, using the space position - components.addAll(Arrays.asList(partialExpression.substring(0, spacePosition + 1).split(" "))); - components.add(partialExpression.substring(spacePosition + 1, closingBracketPosition + 1)); - partialExpression = partialExpression.substring(closingBracketPosition + 1); - } else { - // normal brackets like (1 + 2) * (3 / 5) - 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(""); - } - - // deal with space multiplication (x y) - if (this.spaceOperator != null) { - for (int i = 0; i < components.size() - 1; i++) { - if (this.getTokenType(components.get(i)) == TokenType.OBJECT - && this.getTokenType(components.get(i + 1)) == TokenType.OBJECT) { - components.add(++i, this.spaceOperator); - } - } - } - - // turn the expression into reverse Polish - while (true) { - final int highestPriorityOperatorPosition = this.findHighestPriorityOperatorPosition(components); - if (highestPriorityOperatorPosition == -1) { - break; - } - - // swap components based on what kind of operator there is - // 1 + 2 becomes 2 1 + - // - 1 becomes 1 - - 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; - } - - /** - * 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 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - 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 - * @since v0.2.0 - */ - 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(); - } -} |