Added an expression parser that can parse RPN expressions.

4 files changed, 423 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
index 866d01d..52a523a 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
 bin/
+target/
 *.class
 *~
\ No newline at end of file
diff --git a/CHANGELOG.org b/CHANGELOG.org
index b9c87c9..87e26e0 100644
--- a/CHANGELOG.org
+++ b/CHANGELOG.org
@@ -8,6 +8,7 @@ All notable changes in this project will be shown in this file.
 *** Added
  - GUI for a selection-based unit converter
  - The UnitDatabase now stores dimensions.
+ - A system to parse mathematical expressions, used to parse unit expressions.
 ** v0.1.0
 NOTE: At this stage, the API is subject to significant change.
 *** Added
diff --git a/src/org/unitConverter/expressionParser/ExpressionParser.java b/src/org/unitConverter/expressionParser/ExpressionParser.java
new file mode 100644
index 0000000..804ea87
--- /dev/null
+++ b/src/org/unitConverter/expressionParser/ExpressionParser.java
@@ -0,0 +1,398 @@
+/**
+ * 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.expressionParser;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.HashMap;
+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.
+		 */
+		@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;
+		}
+	}
+
+	/**
+	 * 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.
+		 */
+		@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;
+		}
+	}
+
+	/**
+	 * The types of tokens that are available.
+	 * 
+	 * @author Adrien Hopkins
+	 * @since 2019-03-14
+	 */
+	private static enum TokenType {
+		OBJECT, UNARY_OPERATOR, BINARY_OPERATOR;
+	}
+
+	/**
+	 * 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
+	 * @return
+	 * @since 2019-03-17
+	 */
+	private String convertExpressionToReversePolish(final String expression) {
+		Objects.requireNonNull(expression, "expression must not be null.");
+
+		// TODO method stub org.unitConverter.expressionParser.ExpressionParser.convertExpressionToPolish(expression)
+		throw new UnsupportedOperationException();
+	}
+
+	/**
+	 * 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/expressionParser/package-info.java b/src/org/unitConverter/expressionParser/package-info.java
new file mode 100644
index 0000000..28f0cae
--- /dev/null
+++ b/src/org/unitConverter/expressionParser/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.expressionParser;
\ No newline at end of file