diff options
Diffstat (limited to 'src/main/java/sevenUnits/utils/ExpressionParser.java')
| -rw-r--r-- | src/main/java/sevenUnits/utils/ExpressionParser.java | 308 |
1 files changed, 231 insertions, 77 deletions
diff --git a/src/main/java/sevenUnits/utils/ExpressionParser.java b/src/main/java/sevenUnits/utils/ExpressionParser.java index 941c2a4..e248ff0 100644 --- a/src/main/java/sevenUnits/utils/ExpressionParser.java +++ b/src/main/java/sevenUnits/utils/ExpressionParser.java @@ -1,5 +1,5 @@ /** - * Copyright (C) 2019 Adrien Hopkins + * Copyright (C) 2019, 2024 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 @@ -24,6 +24,7 @@ import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; +import java.util.function.BiFunction; import java.util.function.BinaryOperator; import java.util.function.Function; import java.util.function.UnaryOperator; @@ -55,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) * @@ -63,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. @@ -72,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. @@ -81,7 +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}. * @@ -96,8 +104,9 @@ public final class ExpressionParser<T> { "objectObtainer must not be null."); this.unaryOperators = new HashMap<>(); this.binaryOperators = new HashMap<>(); + this.numericOperators = new HashMap<>(); } - + /** * Adds a binary operator to the builder. * @@ -115,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<>( @@ -124,12 +133,42 @@ 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 + * are applied first + * @return this builder + */ + 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<>( + priority) { + @Override + 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. @@ -141,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. * @@ -167,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<>( @@ -180,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 @@ -189,10 +228,10 @@ public final class ExpressionParser<T> { */ public ExpressionParser<T> build() { return new ExpressionParser<>(this.objectObtainer, this.unaryOperators, - this.binaryOperators, this.spaceFunction); + this.binaryOperators, this.numericOperators, this.spaceFunction); } } - + /** * A binary operator with a priority field that determines which operators * apply first. @@ -212,7 +251,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final int priority; - + /** * Creates the {@code PriorityBinaryOperator}. * @@ -223,7 +262,7 @@ public final class ExpressionParser<T> { public PriorityBinaryOperator(final int priority) { this.priority = priority; } - + /** * Compares this object to another by priority. * @@ -243,7 +282,68 @@ public final class ExpressionParser<T> { else return 0; } - + + /** + * @return priority + * @since 2019-03-22 + * @since v0.2.0 + */ + public final int getPriority() { + 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 + * @since v0.2.0 + */ + 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 + * + * @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 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 + */ + @Override + public int compareTo(final PriorityBiFunction<T, U, R> 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 @@ -253,7 +353,7 @@ public final class ExpressionParser<T> { return this.priority; } } - + /** * A unary operator with a priority field that determines which operators * apply first. @@ -273,7 +373,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private final int priority; - + /** * Creates the {@code PriorityUnaryOperator}. * @@ -284,7 +384,7 @@ public final class ExpressionParser<T> { public PriorityUnaryOperator(final int priority) { this.priority = priority; } - + /** * Compares this object to another by priority. * @@ -304,7 +404,7 @@ public final class ExpressionParser<T> { else return 0; } - + /** * @return priority * @since 2019-03-22 @@ -314,7 +414,7 @@ public final class ExpressionParser<T> { return this.priority; } } - + /** * The types of tokens that are available. * @@ -323,9 +423,9 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ private static enum TokenType { - OBJECT, UNARY_OPERATOR, BINARY_OPERATOR; + OBJECT, UNARY_OPERATOR, BINARY_OPERATOR, NUMERIC_OPERATOR; } - + /** * The opening bracket. * @@ -333,7 +433,7 @@ public final class ExpressionParser<T> { * @since v0.2.0 */ public static final char OPENING_BRACKET = '('; - + /** * The closing bracket. * @@ -341,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. * @@ -355,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) { @@ -374,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) { @@ -392,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}. @@ -404,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. * @@ -412,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. @@ -421,7 +521,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; + /** * The operator for space, or null if spaces have no function. * @@ -429,27 +536,30 @@ 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 spaceOperator operator used by spaces + * @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 * @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 Map<String, PriorityBiFunction<T, UncertainDouble, T>> numericOperators, final String spaceOperator) { this.objectObtainer = objectObtainer; this.unaryOperators = unaryOperators; this.binaryOperators = binaryOperators; + this.numericOperators = numericOperators; this.spaceOperator = spaceOperator; } - + /** * Converts a given mathematical expression to reverse Polish notation * (operators after operands). @@ -468,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) != ' ') { @@ -510,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++) { @@ -528,7 +638,7 @@ public final class ExpressionParser<T> { } } } - + // turn the expression into reverse Polish while (true) { final int highestPriorityOperatorPosition = this @@ -536,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 - @@ -554,6 +664,7 @@ public final class ExpressionParser<T> { operand + " " + unaryOperator); break; case BINARY_OPERATOR: + case NUMERIC_OPERATOR: if (components.size() < 3) throw new IllegalArgumentException( "Invalid expression \"" + expression + "\""); @@ -570,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); } @@ -583,7 +694,7 @@ public final class ExpressionParser<T> { } return expressionRPN; } - + /** * Finds the position of the highest-priority operator in a list * @@ -601,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; @@ -622,21 +733,31 @@ 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; } break; + case NUMERIC_OPERATOR: + final PriorityBiFunction<T, UncertainDouble, T> numericOperator = this.numericOperators + .get(components.get(i)); + final int numericPriority = numericOperator.getPriority(); + + if (numericPriority > maxPriority) { + maxPriority = numericPriority; + maxPriorityPosition = i; + } + break; default: break; } } - + // max priority position found return maxPriorityPosition; } - + /** * Determines whether an inputted string is an object or an operator * @@ -648,15 +769,17 @@ 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)) return TokenType.BINARY_OPERATOR; + else if (this.numericOperators.containsKey(token)) + return TokenType.NUMERIC_OPERATOR; else return TokenType.OBJECT; } - + /** * Parses an expression. * @@ -670,7 +793,7 @@ public final class ExpressionParser<T> { return this.parseReversePolishExpression( this.convertExpressionToReversePolish(expression)); } - + /** * Parses an expression expressed in reverse Polish notation. * @@ -682,55 +805,86 @@ 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); + stack.push(op.apply(ot, on)); + break; + case OBJECT: // just add it to the stack - stack.push(this.objectObtainer.apply(item)); + // these try-catch statements are necessary + // to make the code as generalizable as possible + // also they're required for number formatting code because + // that's the only way to tell if an expression is a number or not. + try { + stack.push(this.objectObtainer.apply(item)); + } catch (Exception e) { + try { + doubleStack.push(UncertainDouble.fromString(item)); + } catch (IllegalArgumentException e2) { + try { + 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( |