diff options
Diffstat (limited to 'src/main/java/sevenUnits/utils/ExpressionParser.java')
| -rw-r--r-- | src/main/java/sevenUnits/utils/ExpressionParser.java | 334 |
1 files changed, 164 insertions, 170 deletions
diff --git a/src/main/java/sevenUnits/utils/ExpressionParser.java b/src/main/java/sevenUnits/utils/ExpressionParser.java index 783a135..03c763c 100644 --- a/src/main/java/sevenUnits/utils/ExpressionParser.java +++ b/src/main/java/sevenUnits/utils/ExpressionParser.java @@ -31,7 +31,7 @@ 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 @@ -40,7 +40,7 @@ import java.util.function.UnaryOperator; 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 @@ -51,49 +51,49 @@ public final class ExpressionParser<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; - + /** * A map mapping operator strings to numeric functions. - * + * * @since 2024-03-23 * @since v0.5.0 */ private final Map<String, PriorityBiFunction<T, UncertainDouble, T>> numericOperators; - + /** * 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 @@ -107,10 +107,10 @@ public final class ExpressionParser<T> { this.binaryOperators = new HashMap<>(); this.numericOperators = 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 @@ -125,7 +125,7 @@ public final class ExpressionParser<T> { 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<>( @@ -134,16 +134,16 @@ public final class ExpressionParser<T> { public T apply(final T t, final T u) { return operator.apply(t, u); } - + }; this.binaryOperators.put(text, priorityOperator); return this; } - + /** * Adds a two-argument operator where the second operator is a number. * This is used for operations like vector scaling and exponentation. - * + * * @param text text used to reference the operator, like '^' * @param operator operator to add * @param priority operator's priority, which determines which operators @@ -155,7 +155,7 @@ public final class ExpressionParser<T> { 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 PriorityBiFunction<T, UncertainDouble, T> priorityOperator = new PriorityBiFunction<>( @@ -164,16 +164,16 @@ public final class ExpressionParser<T> { public T apply(final T t, final UncertainDouble u) { return operator.apply(t, u); } - + }; this.numericOperators.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 @@ -181,18 +181,18 @@ public final class ExpressionParser<T> { */ 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 @@ -207,7 +207,7 @@ public final class ExpressionParser<T> { 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<>( @@ -220,7 +220,7 @@ public final class ExpressionParser<T> { this.unaryOperators.put(text, priorityOperator); return this; } - + /** * @return an {@code ExpressionParser<T>} instance with the properties * given to this builder @@ -232,11 +232,11 @@ public final class ExpressionParser<T> { this.binaryOperators, this.numericOperators, 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 @@ -247,15 +247,15 @@ public final class ExpressionParser<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 @@ -263,14 +263,14 @@ public final class ExpressionParser<T> { public PriorityBiFunction(final int priority) { this.priority = priority; } - + /** * Compares this object to another by priority. - * + * * <p> * {@inheritDoc} * </p> - * + * * @since 2019-03-17 * @since v0.2.0 */ @@ -278,12 +278,11 @@ public final class ExpressionParser<T> { public int compareTo(final PriorityBiFunction<T, U, R> o) { if (this.priority < o.priority) return -1; - else if (this.priority > o.priority) + if (this.priority > o.priority) return 1; - else - return 0; + return 0; } - + /** * @return priority * @since 2019-03-22 @@ -293,11 +292,11 @@ public final class ExpressionParser<T> { return this.priority; } } - + /** * 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 @@ -308,15 +307,15 @@ public final class ExpressionParser<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 @@ -324,14 +323,14 @@ public final class ExpressionParser<T> { 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 */ @@ -339,12 +338,11 @@ public final class ExpressionParser<T> { public int compareTo(final PriorityBinaryOperator<T> o) { if (this.priority < o.priority) return -1; - else if (this.priority > o.priority) + if (this.priority > o.priority) return 1; - else - return 0; + return 0; } - + /** * @return priority * @since 2019-03-22 @@ -354,11 +352,11 @@ public final class ExpressionParser<T> { 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 @@ -369,15 +367,15 @@ public final class ExpressionParser<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 @@ -385,14 +383,14 @@ public final class ExpressionParser<T> { 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 */ @@ -400,12 +398,11 @@ public final class ExpressionParser<T> { public int compareTo(final PriorityUnaryOperator<T> o) { if (this.priority < o.priority) return -1; - else if (this.priority > o.priority) + if (this.priority > o.priority) return 1; - else - return 0; + return 0; } - + /** * @return priority * @since 2019-03-22 @@ -415,37 +412,37 @@ public final class ExpressionParser<T> { 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 { + private enum TokenType { OBJECT, UNARY_OPERATOR, BINARY_OPERATOR, NUMERIC_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 @@ -456,9 +453,9 @@ public final class ExpressionParser<T> { private static int findBracketPair(final String string, final int bracketPosition) { Objects.requireNonNull(string, "string must not be null."); - - final char openingBracket = string.charAt(bracketPosition); - + + final var openingBracket = string.charAt(bracketPosition); + // figure out what closing bracket to look for final char closingBracket; switch (openingBracket) { @@ -475,16 +472,16 @@ public final class ExpressionParser<T> { 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; - + var bracketLevel = 0; + // iterate over the string to find the closing bracket - for (int currentPosition = bracketPosition; currentPosition < string + for (var currentPosition = bracketPosition; currentPosition < string .length(); currentPosition++) { - final char currentCharacter = string.charAt(currentPosition); - + final var currentCharacter = string.charAt(currentPosition); + if (currentCharacter == openingBracket) { bracketLevel++; } else if (currentCharacter == closingBracket) { @@ -493,55 +490,55 @@ public final class ExpressionParser<T> { 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; - + /** * A map mapping operator strings to numeric functions. - * + * * @since 2024-03-23 * @since v0.5.0 */ private final Map<String, PriorityBiFunction<T, UncertainDouble, T>> numericOperators; - + /** * 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 @@ -561,7 +558,7 @@ public final class ExpressionParser<T> { this.numericOperators = numericOperators; this.spaceOperator = spaceOperator; } - + /** * Converts a given mathematical expression to reverse Polish notation * (operators after operands). @@ -570,7 +567,7 @@ public final class ExpressionParser<T> { * {@code 2 * (3 + 4)}<br> * becomes<br> * {@code 2 3 4 + *}. - * + * * @param expression expression * @return expression in RPN * @throws IllegalArgumentException if expression is invalid (e.g. @@ -580,25 +577,25 @@ public final class ExpressionParser<T> { */ 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; - + var partialExpression = expression; + // find and deal with brackets while (partialExpression.indexOf(OPENING_BRACKET) != -1) { - final int openingBracketPosition = partialExpression + final var openingBracketPosition = partialExpression .indexOf(OPENING_BRACKET); - final int closingBracketPosition = findBracketPair(partialExpression, + final var 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; + var spacePosition = openingBracketPosition; while (spacePosition >= 0 && partialExpression.charAt(spacePosition) != ' ') { spacePosition--; @@ -609,8 +606,6 @@ public final class ExpressionParser<T> { .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 @@ -618,37 +613,37 @@ public final class ExpressionParser<T> { components.add(this.convertExpressionToReversePolish( partialExpression.substring(openingBracketPosition + 1, closingBracketPosition))); - partialExpression = partialExpression - .substring(closingBracketPosition + 1); } + 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++) { + for (var 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 + final var 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 - @@ -658,9 +653,9 @@ public final class ExpressionParser<T> { if (components.size() < 2) throw new IllegalArgumentException( "Invalid expression \"" + expression + "\""); - final String unaryOperator = components + final var unaryOperator = components .remove(highestPriorityOperatorPosition); - final String operand = components + final var operand = components .remove(highestPriorityOperatorPosition); components.add(highestPriorityOperatorPosition, operand + " " + unaryOperator); @@ -670,11 +665,11 @@ public final class ExpressionParser<T> { if (components.size() < 3) throw new IllegalArgumentException( "Invalid expression \"" + expression + "\""); - final String binaryOperator = components + final var binaryOperator = components .remove(highestPriorityOperatorPosition); - final String operand1 = components + final var operand1 = components .remove(highestPriorityOperatorPosition - 1); - final String operand2 = components + final var operand2 = components .remove(highestPriorityOperatorPosition - 1); components.add(highestPriorityOperatorPosition - 1, operand1 + " " + operand2 + " " + binaryOperator); @@ -683,7 +678,7 @@ public final class ExpressionParser<T> { throw new AssertionError("Expected operator, found non-operator."); } } - + // join all of the components together, then ensure there is only one // space in a row if (components.size() != 1) @@ -691,10 +686,10 @@ public final class ExpressionParser<T> { "Invalid expression \"" + expression + "\"."); return components.get(0).replaceAll(" +", " ").trim(); } - + /** * 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 @@ -707,40 +702,40 @@ public final class ExpressionParser<T> { final List<String> components) { Objects.requireNonNull(components, "components must not be null."); // find highest priority - int maxPriority = Integer.MIN_VALUE; - int maxPriorityPosition = -1; - + var maxPriority = Integer.MIN_VALUE; + var 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++) { - + for (var i = 0; i < components.size(); i++) { + switch (this.getTokenType(components.get(i))) { case UNARY_OPERATOR: - final PriorityUnaryOperator<T> unaryOperator = this.unaryOperators + final var unaryOperator = this.unaryOperators .get(components.get(i)); - final int unaryPriority = unaryOperator.getPriority(); - + final var unaryPriority = unaryOperator.getPriority(); + if (unaryPriority > maxPriority) { maxPriority = unaryPriority; maxPriorityPosition = i; } break; case BINARY_OPERATOR: - final PriorityBinaryOperator<T> binaryOperator = this.binaryOperators + final var binaryOperator = this.binaryOperators .get(components.get(i)); - final int binaryPriority = binaryOperator.getPriority(); - + final var binaryPriority = binaryOperator.getPriority(); + if (binaryPriority > maxPriority) { maxPriority = binaryPriority; maxPriorityPosition = i; } break; case NUMERIC_OPERATOR: - final PriorityBiFunction<T, UncertainDouble, T> numericOperator = this.numericOperators + final var numericOperator = this.numericOperators .get(components.get(i)); - final int numericPriority = numericOperator.getPriority(); - + final var numericPriority = numericOperator.getPriority(); + if (numericPriority > maxPriority) { maxPriority = numericPriority; maxPriorityPosition = i; @@ -750,14 +745,14 @@ public final class ExpressionParser<T> { 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 @@ -766,20 +761,19 @@ public final class ExpressionParser<T> { */ 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)) + if (this.binaryOperators.containsKey(token)) return TokenType.BINARY_OPERATOR; - else if (this.numericOperators.containsKey(token)) + if (this.numericOperators.containsKey(token)) return TokenType.NUMERIC_OPERATOR; - else - return TokenType.OBJECT; + return TokenType.OBJECT; } - + /** * Parses an expression. - * + * * @param expression expression to parse * @return result * @throws NullPointerException if {@code expression} is null @@ -790,10 +784,10 @@ public final class ExpressionParser<T> { 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 @@ -802,43 +796,43 @@ public final class ExpressionParser<T> { */ T parseReversePolishExpression(final String expression) { Objects.requireNonNull(expression, "expression must not be null."); - + final Deque<T> stack = new ArrayDeque<>(); final Deque<UncertainDouble> doubleStack = 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 var o1 = stack.pop(); + final var o2 = stack.pop(); final BinaryOperator<T> binaryOperator = this.binaryOperators .get(item); - + stack.push(binaryOperator.apply(o2, o1)); break; - + case NUMERIC_OPERATOR: if (stack.size() < 1 || doubleStack.size() < 1) throw new IllegalStateException(String.format( "Attempted to call binary operator %s with insufficient arguments.", item)); - - final T ot = stack.pop(); - final UncertainDouble on = doubleStack.pop(); + + final var ot = stack.pop(); + final var on = doubleStack.pop(); final BiFunction<T, UncertainDouble, T> op = this.numericOperators .get(item); stack.push(op.apply(ot, on)); break; - + case OBJECT: // just add it to the stack // these try-catch statements are necessary @@ -860,33 +854,33 @@ public final class ExpressionParser<T> { } } 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 var 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) + if (stack.size() == 0) throw new IllegalStateException( "Computation ended up without an answer."); return stack.pop(); |