diff options
Diffstat (limited to 'src/main/java/sevenUnits/utils/ExpressionParser.java')
| -rw-r--r-- | src/main/java/sevenUnits/utils/ExpressionParser.java | 184 |
1 files changed, 95 insertions, 89 deletions
diff --git a/src/main/java/sevenUnits/utils/ExpressionParser.java b/src/main/java/sevenUnits/utils/ExpressionParser.java index a41f37d..e248ff0 100644 --- a/src/main/java/sevenUnits/utils/ExpressionParser.java +++ b/src/main/java/sevenUnits/utils/ExpressionParser.java @@ -56,7 +56,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final Function<String, ? extends T> objectObtainer; - + /** * The function of the space as an operator (like 3 x y) * @@ -64,7 +64,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private String spaceFunction = null; - + /** * A map mapping operator strings to operator functions, for unary * operators. @@ -73,7 +73,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final Map<String, PriorityUnaryOperator<T>> unaryOperators; - + /** * A map mapping operator strings to operator functions, for binary * operators. @@ -82,14 +82,14 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final Map<String, PriorityBinaryOperator<T>> binaryOperators; - + /** * A map mapping operator strings to numeric functions. * * @since 2024-03-23 */ private final Map<String, PriorityBiFunction<T, UncertainDouble, T>> numericOperators; - + /** * Creates the {@code Builder}. * @@ -106,7 +106,7 @@ public final class ExpressionParser<T> { this.binaryOperators = new HashMap<>(); this.numericOperators = new HashMap<>(); } - + /** * Adds a binary operator to the builder. * @@ -124,7 +124,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<>( @@ -133,24 +133,28 @@ 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. + * 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 * are applied first * @return this builder */ - public Builder<T> addNumericOperator(final String text, final BiFunction<T, UncertainDouble, T> operator, final int priority) { + public Builder<T> addNumericOperator(final String text, + final BiFunction<T, UncertainDouble, 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 PriorityBiFunction<T, UncertainDouble, T> priorityOperator = new PriorityBiFunction<>( @@ -159,12 +163,12 @@ 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. @@ -176,15 +180,15 @@ 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. * @@ -202,7 +206,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<>( @@ -215,7 +219,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 @@ -227,7 +231,7 @@ public final class ExpressionParser<T> { this.binaryOperators, this.numericOperators, this.spaceFunction); } } - + /** * A binary operator with a priority field that determines which operators * apply first. @@ -247,7 +251,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final int priority; - + /** * Creates the {@code PriorityBinaryOperator}. * @@ -258,7 +262,7 @@ public final class ExpressionParser<T> { public PriorityBinaryOperator(final int priority) { this.priority = priority; } - + /** * Compares this object to another by priority. * @@ -278,7 +282,7 @@ public final class ExpressionParser<T> { else return 0; } - + /** * @return priority * @since 2019-03-22 @@ -298,8 +302,8 @@ public final class ExpressionParser<T> { * @since 2019-03-17 * @since v0.2.0 */ - private static abstract class PriorityBiFunction<T, U, R> - implements BiFunction<T, U, R>, Comparable<PriorityBiFunction<T, U, R>> { + private static abstract class PriorityBiFunction<T, U, R> implements + BiFunction<T, U, R>, Comparable<PriorityBiFunction<T, U, R>> { /** * The operator's priority. Higher-priority operators are applied before * lower-priority operators @@ -308,7 +312,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final int priority; - + /** * Creates the {@code PriorityBinaryOperator}. * @@ -319,7 +323,7 @@ public final class ExpressionParser<T> { public PriorityBiFunction(final int priority) { this.priority = priority; } - + /** * Compares this object to another by priority. * @@ -339,7 +343,7 @@ public final class ExpressionParser<T> { else return 0; } - + /** * @return priority * @since 2019-03-22 @@ -349,7 +353,7 @@ public final class ExpressionParser<T> { return this.priority; } } - + /** * A unary operator with a priority field that determines which operators * apply first. @@ -369,7 +373,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final int priority; - + /** * Creates the {@code PriorityUnaryOperator}. * @@ -380,7 +384,7 @@ public final class ExpressionParser<T> { public PriorityUnaryOperator(final int priority) { this.priority = priority; } - + /** * Compares this object to another by priority. * @@ -400,7 +404,7 @@ public final class ExpressionParser<T> { else return 0; } - + /** * @return priority * @since 2019-03-22 @@ -410,7 +414,7 @@ public final class ExpressionParser<T> { return this.priority; } } - + /** * The types of tokens that are available. * @@ -421,7 +425,7 @@ public final class ExpressionParser<T> { private static enum TokenType { OBJECT, UNARY_OPERATOR, BINARY_OPERATOR, NUMERIC_OPERATOR; } - + /** * The opening bracket. * @@ -429,7 +433,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ public static final char OPENING_BRACKET = '('; - + /** * The closing bracket. * @@ -437,7 +441,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ public static final char CLOSING_BRACKET = ')'; - + /** * Finds the other bracket in a pair of brackets, given the position of one. * @@ -451,9 +455,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); - + // figure out what closing bracket to look for final char closingBracket; switch (openingBracket) { @@ -470,16 +474,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; - + // 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) { @@ -488,10 +492,10 @@ 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}. @@ -500,7 +504,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final Function<String, ? extends T> objectObtainer; - + /** * A map mapping operator strings to operator functions, for unary operators. * @@ -508,7 +512,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final Map<String, PriorityUnaryOperator<T>> unaryOperators; - + /** * A map mapping operator strings to operator functions, for binary * operators. @@ -524,7 +528,7 @@ public final class ExpressionParser<T> { * @since 2024-03-23 */ private final Map<String, PriorityBiFunction<T, UncertainDouble, T>> numericOperators; - + /** * The operator for space, or null if spaces have no function. * @@ -532,15 +536,15 @@ public final class ExpressionParser<T> { * @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 objectObtainer function to get objects from strings + * @param unaryOperators unary operators available to the parser + * @param binaryOperators binary operators available to the parser * @param numericOperators numeric operators available to the parser - * @param spaceOperator operator used by spaces + * @param spaceOperator operator used by spaces * @since 2019-03-14 * @since v0.2.0 */ @@ -555,7 +559,7 @@ public final class ExpressionParser<T> { this.numericOperators = numericOperators; this.spaceOperator = spaceOperator; } - + /** * Converts a given mathematical expression to reverse Polish notation * (operators after operands). @@ -574,19 +578,19 @@ 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; - + // 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) != ' ') { @@ -616,15 +620,15 @@ public final class ExpressionParser<T> { .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++) { @@ -634,7 +638,7 @@ public final class ExpressionParser<T> { } } } - + // turn the expression into reverse Polish while (true) { final int highestPriorityOperatorPosition = this @@ -642,7 +646,7 @@ public final class ExpressionParser<T> { if (highestPriorityOperatorPosition == -1) { break; } - + // swap components based on what kind of operator there is // 1 + 2 becomes 2 1 + // - 1 becomes 1 - @@ -677,11 +681,11 @@ 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 String expressionRPN = String.join(" ", components).replaceAll(" +", " "); - + while (expressionRPN.charAt(0) == ' ') { expressionRPN = expressionRPN.substring(1); } @@ -690,7 +694,7 @@ public final class ExpressionParser<T> { } return expressionRPN; } - + /** * Finds the position of the highest-priority operator in a list * @@ -708,18 +712,18 @@ public final class ExpressionParser<T> { // 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; @@ -729,7 +733,7 @@ public final class ExpressionParser<T> { final PriorityBinaryOperator<T> binaryOperator = this.binaryOperators .get(components.get(i)); final int binaryPriority = binaryOperator.getPriority(); - + if (binaryPriority > maxPriority) { maxPriority = binaryPriority; maxPriorityPosition = i; @@ -739,7 +743,7 @@ public final class ExpressionParser<T> { final PriorityBiFunction<T, UncertainDouble, T> numericOperator = this.numericOperators .get(components.get(i)); final int numericPriority = numericOperator.getPriority(); - + if (numericPriority > maxPriority) { maxPriority = numericPriority; maxPriorityPosition = i; @@ -749,11 +753,11 @@ public final class ExpressionParser<T> { break; } } - + // max priority position found return maxPriorityPosition; } - + /** * Determines whether an inputted string is an object or an operator * @@ -765,7 +769,7 @@ 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)) @@ -775,7 +779,7 @@ public final class ExpressionParser<T> { else return TokenType.OBJECT; } - + /** * Parses an expression. * @@ -789,7 +793,7 @@ public final class ExpressionParser<T> { return this.parseReversePolishExpression( this.convertExpressionToReversePolish(expression)); } - + /** * Parses an expression expressed in reverse Polish notation. * @@ -801,42 +805,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 BinaryOperator<T> binaryOperator = this.binaryOperators .get(item); - + stack.push(binaryOperator.apply(o1, o2)); 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 BiFunction<T, UncertainDouble, T> op = this.numericOperators.get(item); + 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 @@ -850,35 +855,36 @@ public final class ExpressionParser<T> { doubleStack.push(UncertainDouble.fromString(item)); } catch (IllegalArgumentException e2) { try { - doubleStack.push(UncertainDouble.of(Double.parseDouble(item), 0)); + doubleStack.push( + UncertainDouble.of(Double.parseDouble(item), 0)); } catch (NumberFormatException e3) { throw e; } } } 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( |