Add DualExprParser

This class parses DualExprs from prefix expressions

6 files changed, 419 insertions, 60 deletions

diff --git a/base/src/main/java/bjc/utils/exceptions/InvalidToken.java b/base/src/main/java/bjc/utils/exceptions/InvalidToken.java
new file mode 100644
index 0000000..b09af78
--- /dev/null
+++ b/base/src/main/java/bjc/utils/exceptions/InvalidToken.java
@@ -0,0 +1,9 @@
+package bjc.utils.exceptions;
+
+public class InvalidToken extends RuntimeException {
+	private static final long serialVersionUID = -5077165766341244689L;
+
+	public InvalidToken(String tok) {
+		super(String.format("Did not recognize token '%s' as a valid token", tok));
+	}
+}
\ No newline at end of file
diff --git a/base/src/main/java/bjc/utils/exceptions/NonConstantPower.java b/base/src/main/java/bjc/utils/exceptions/NonConstantPower.java
new file mode 100644
index 0000000..143fb4d
--- /dev/null
+++ b/base/src/main/java/bjc/utils/exceptions/NonConstantPower.java
@@ -0,0 +1,9 @@
+package bjc.utils.exceptions;
+
+public class NonConstantPower extends RuntimeException {
+	private static final long serialVersionUID = 1640883448305031149L;
+
+	public NonConstantPower() {
+		super("Cannot raise an expression to a non-constant power");
+	}
+}
\ No newline at end of file
diff --git a/base/src/main/java/bjc/utils/exceptions/OperandsRemaining.java b/base/src/main/java/bjc/utils/exceptions/OperandsRemaining.java
new file mode 100644
index 0000000..ca83b30
--- /dev/null
+++ b/base/src/main/java/bjc/utils/exceptions/OperandsRemaining.java
@@ -0,0 +1,28 @@
+package bjc.utils.exceptions;
+
+/**
+ * Exception thrown when an operation has finished, but still has more input
+ * that has not been processed.
+ * 
+ * @author Ben Culkin
+ *
+ */
+public class OperandsRemaining extends RuntimeException {
+	private static final long serialVersionUID = 4848222659854671315L;
+
+	/**
+	 * Create a new OperandsRemaining exception with a default message.
+	 */
+	public OperandsRemaining() {
+		super("Operation had input left-over");
+	}
+	
+	/**
+	 * Create a new OperandsRemaining exception with a specific message.
+	 * 
+	 * @param msg The message of the exception.
+	 */
+	public OperandsRemaining(String msg) {
+		super(msg);
+	}
+}
diff --git a/base/src/main/java/bjc/utils/math/DualExpr.java b/base/src/main/java/bjc/utils/math/DualExpr.java
index 4d21413..81ee31c 100644
--- a/base/src/main/java/bjc/utils/math/DualExpr.java
+++ b/base/src/main/java/bjc/utils/math/DualExpr.java
@@ -81,15 +81,9 @@ public class DualExpr {
 	public DualExpr right;
 
 	/**
-	 * The power to use, for power operations.
-	 */
-	public int power;
-
-	/**
 	 * Create a new constant dual number.
 	 *
-	 * @param num
-	 *        The value of the dual number.
+	 * @param num The value of the dual number.
 	 */
 	public DualExpr(Dual num) {
 		this.type = ExprType.CONSTANT;
@@ -100,10 +94,8 @@ public class DualExpr {
 	/**
 	 * Create a new unary dual number.
 	 *
-	 * @param type
-	 *        The type of operation to perform.
-	 * @param val
-	 *        The parameter to the value.
+	 * @param type The type of operation to perform.
+	 * @param val  The parameter to the value.
 	 */
 	public DualExpr(DualExpr.ExprType type, DualExpr val) {
 		this.type = type;
@@ -114,12 +106,9 @@ public class DualExpr {
 	/**
 	 * Create a new binary dual number.
 	 *
-	 * @param type
-	 *        The type of operation to perform.
-	 * @param left
-	 *        The left hand side of the expression.
-	 * @param right
-	 *        The right hand side of the expression.
+	 * @param type  The type of operation to perform.
+	 * @param left  The left hand side of the expression.
+	 * @param right The right hand side of the expression.
 	 */
 	public DualExpr(DualExpr.ExprType type, DualExpr left, DualExpr right) {
 		this.type = type;
@@ -129,21 +118,6 @@ public class DualExpr {
 	}
 
 	/**
-	 * Create a new power expression.
-	 *
-	 * @param left
-	 *        The expression to raise.
-	 * @param power
-	 *        The power to raise it by.
-	 */
-	public DualExpr(DualExpr left, int power) {
-		this.type = ExprType.POWER;
-
-		this.left = left;
-		this.power = power;
-	}
-
-	/**
 	 * Evaluate an expression to a number.
 	 *
 	 * Uses the rules provided in
@@ -156,7 +130,7 @@ public class DualExpr {
 		Dual lval, rval;
 
 		/* Perform the right operation for each type. */
-		switch(type) {
+		switch (type) {
 		case CONSTANT:
 			return number;
 		case ADDITION:
@@ -184,7 +158,7 @@ public class DualExpr {
 			rval = right.evaluate();
 
 		{
-			if(rval.real == 0) {
+			if (rval.real == 0) {
 				throw new IllegalArgumentException("ERROR: Attempted to divide by zero.");
 			}
 
@@ -214,24 +188,32 @@ public class DualExpr {
 		case LOGARITHM:
 			lval = left.evaluate();
 
-			if(lval.real <= 0) {
+			if (lval.real <= 0) {
 				throw new IllegalArgumentException("ERROR: Attempted to take non-positive log.");
 			}
 
 			return new Dual(Math.log(lval.real), lval.dual / lval.real);
 		case POWER:
+			// @TODO Ben Culkin 3/27/2020 :RealPower
+			// Make this no longer a special case; since it doesn't have to be one.
+			//
+			// 3/28/2020 - This is less of a special case, but I've not implemented the bit for variable exponents.
 			lval = left.evaluate();
+			rval = right.evaluate();
 
-			if(lval.real == 0) {
+			if (lval.real == 0) {
 				throw new IllegalArgumentException("ERROR: Raising zero to a power.");
 			}
 
-		{
-			double rl = Math.pow(lval.real, power);
+			if (rval.dual != 0.0) {
+				throw new IllegalArgumentException(
+						"ERROR: Powers with a non-zero dual component not currently implemented");
+			} {
+			double rl = Math.pow(lval.real, rval.real);
 
-			double lft = Math.pow(lval.real, power - 1);
+			double lft = Math.pow(lval.real, rval.real - 1);
 
-			return new Dual(rl, power * lft * lval.dual);
+			return new Dual(rl, rval.real * lft * lval.dual);
 		}
 		case ABSOLUTE:
 			lval = left.evaluate();
@@ -246,7 +228,7 @@ public class DualExpr {
 
 	@Override
 	public String toString() {
-		switch(type) {
+		switch (type) {
 		case ABSOLUTE:
 			return String.format("abs(%s)", left.toString());
 		case ADDITION:
@@ -264,7 +246,7 @@ public class DualExpr {
 		case MULTIPLICATION:
 			return String.format("(%s * %s)", left.toString(), right.toString());
 		case POWER:
-			return String.format("(%s ^ %d)", left.toString(), power);
+			return String.format("(%s ^ %d)", left.toString(), right.toString());
 		case SIN:
 			return String.format("sin(%s)", left.toString());
 		case SUBTRACTION:
@@ -281,7 +263,6 @@ public class DualExpr {
 
 		result = prime * result + ((left == null) ? 0 : left.hashCode());
 		result = prime * result + ((number == null) ? 0 : number.hashCode());
-		result = prime * result + power;
 		result = prime * result + ((right == null) ? 0 : right.hashCode());
 		result = prime * result + ((type == null) ? 0 : type.hashCode());
 
@@ -290,39 +271,39 @@ public class DualExpr {
 
 	@Override
 	public boolean equals(Object obj) {
-		if(this == obj) return true;
-		if(obj == null) return false;
-		if(getClass() != obj.getClass()) return false;
+		if (this == obj)
+			return true;
+		if (obj == null)
+			return false;
+		if (getClass() != obj.getClass())
+			return false;
 
 		DualExpr other = (DualExpr) obj;
 
-		if(type != other.type) {
+		if (type != other.type) {
 			return false;
 		}
 
-		if(left == null) {
-			if(other.left != null) {
+		if (left == null) {
+			if (other.left != null) {
 				return false;
 			}
-		} else if(!left.equals(other.left)) {
+		} else if (!left.equals(other.left)) {
 			return false;
 		}
 
-		if(right == null) {
-			if(other.right != null) {
+		if (right == null) {
+			if (other.right != null) {
 				return false;
 			}
-		} else if(!right.equals(other.right)) {
+		} else if (!right.equals(other.right)) {
 			return false;
 		}
 
-		if(number == null) {
-			if(other.number != null) return false;
-		} else if(!number.equals(other.number)) {
-			return false;
-		}
-
-		if(power != other.power) {
+		if (number == null) {
+			if (other.number != null)
+				return false;
+		} else if (!number.equals(other.number)) {
 			return false;
 		}
 
diff --git a/base/src/main/java/bjc/utils/math/DualExprParser.java b/base/src/main/java/bjc/utils/math/DualExprParser.java
new file mode 100644
index 0000000..71d62c7
--- /dev/null
+++ b/base/src/main/java/bjc/utils/math/DualExprParser.java
@@ -0,0 +1,200 @@
+/**
+ * 
+ */
+package bjc.utils.math;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import bjc.utils.esodata.SimpleStack;
+import bjc.utils.esodata.Stack;
+import bjc.utils.esodata.Stack.StackUnderflowException;
+import bjc.utils.exceptions.InvalidToken;
+import bjc.utils.exceptions.NonConstantPower;
+import bjc.utils.exceptions.OperandsRemaining;
+import bjc.utils.math.DualExpr.ExprType;
+
+/**
+ * Create DualExprs from strings.
+ * 
+ * @author Ben Culkin
+ *
+ */
+public class DualExprParser {
+	public static class Result {
+		public DualExpr expr;
+		public Map<String, DualExpr> varMap;
+
+		public Result() {
+			this.varMap = new HashMap<>();
+		}
+	}
+
+	/**
+	 * Parses a dual expression from a postfix expression string.
+	 * 
+	 * @param expr    The string to parse the dual expression from.
+	 *
+	 * @param preVars Any pre-existing variables to use.
+	 * 
+	 * @return Both the parsed expression, and a map of all the variables used
+	 */
+	public static Result parseExpression(String expr) {
+		return parseExpression(expr, null);
+	}
+
+	/**
+	 * Parses a dual expression from a postfix expression string.
+	 * 
+	 * @param expr    The string to parse the dual expression from.
+	 *
+	 * @param preVars Any pre-existing variables to use.
+	 * 
+	 * @return Both the parsed expression, and a map of all the variables used
+	 * 
+	 * @throws StackUnderflowException If the expression is not properly formatted.
+	 */
+	public static Result parseExpression(String expr, Map<String, DualExpr> preVars) {
+		Result res = new Result();
+
+		if (preVars == null) {
+		} else {
+			res.varMap = preVars;
+		}
+
+		Map<String, DualExpr> vars = res.varMap;
+
+		String[] tokens = expr.split(" ");
+
+		Stack<DualExpr> exprStack = new SimpleStack<>();
+
+		for (int idx = 0; idx < tokens.length; idx++) {
+			String token = tokens[idx];
+
+			switch (token) {
+			case "add":
+			case "+": {
+				DualExpr rhs = exprStack.pop();
+				DualExpr lhs = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.ADDITION, lhs, rhs));
+				break;
+			}
+			case "subtract":
+			case "-": {
+				DualExpr rhs = exprStack.pop();
+				DualExpr lhs = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.SUBTRACTION, lhs, rhs));
+				break;
+			}
+			case "multiply":
+			case "*": {
+				DualExpr rhs = exprStack.pop();
+				DualExpr lhs = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.MULTIPLICATION, lhs, rhs));
+				break;
+			}
+			case "divide":
+			case "/": {
+				DualExpr rhs = exprStack.pop();
+				DualExpr lhs = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.DIVISION, lhs, rhs));
+				break;
+			}
+			case "abs": {
+				DualExpr opr = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.ABSOLUTE, opr));
+				break;
+			}
+			case "log": {
+				DualExpr opr = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.LOGARITHM, opr));
+				break;
+			}
+			case "sin": {
+				DualExpr opr = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.SIN, opr));
+				break;
+			}
+			case "cos": {
+				DualExpr opr = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.COS, opr));
+				break;
+			}
+			case "exp": {
+				DualExpr opr = exprStack.pop();
+
+				exprStack.push(new DualExpr(ExprType.EXPONENTIAL, opr));
+				break;
+			}
+			case "pow": {
+				DualExpr pow = exprStack.pop();
+				DualExpr bod = exprStack.pop();
+
+				{
+					Dual val = pow.number;
+					if (val.dual != 0)
+						throw new NonConstantPower();
+				}
+
+				exprStack.push(new DualExpr(ExprType.POWER, bod, pow));
+				break;
+			}
+			case "eval": {
+				DualExpr exp = exprStack.pop();
+
+				exprStack.push(new DualExpr(exp.evaluate()));
+				break;
+			}
+			case "dual": {
+				DualExpr dual = exprStack.pop();
+				DualExpr real = exprStack.pop();
+
+				exprStack.push(new DualExpr(new Dual(real.evaluate().real, dual.evaluate().real)));
+				break;
+			}
+			default:
+				if (token.matches("[a-zA-Z][a-zA-Z0-9]*")) {
+					if (vars.containsKey(token)) {
+						exprStack.push(vars.get(token));
+					} else {
+						Dual var = new Dual();
+						DualExpr varExpr = new DualExpr(var);
+
+						vars.put(token, varExpr);
+
+						exprStack.push(varExpr);
+					}
+				} else {
+					try {
+						double d = Double.parseDouble(token);
+
+						exprStack.push(new DualExpr(new Dual(d)));
+					} catch (NumberFormatException nfex) {
+						throw new InvalidToken(token);
+					}
+				}
+
+				break;
+			}
+		}
+
+		if (res.expr == null) {
+			res.expr = exprStack.pop();
+		}
+
+		if (exprStack.size() > 0)
+			throw new OperandsRemaining(String.format(
+					"After processing expression, not all values had been consumed.\n\tRemaining values are '%s'",
+					exprStack.toString()));
+
+		return res;
+	}
+}
\ No newline at end of file
diff --git a/base/src/test/java/bjc/utils/test/math/DualExprParserTest.java b/base/src/test/java/bjc/utils/test/math/DualExprParserTest.java
new file mode 100644
index 0000000..1960b53
--- /dev/null
+++ b/base/src/test/java/bjc/utils/test/math/DualExprParserTest.java
@@ -0,0 +1,132 @@
+package bjc.utils.test.math;
+
+import static org.junit.Assert.*;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import org.junit.Test;
+
+import bjc.utils.exceptions.NonConstantPower;
+import bjc.utils.exceptions.OperandsRemaining;
+import bjc.utils.math.Dual;
+import bjc.utils.math.DualExpr;
+import bjc.utils.math.DualExprParser;
+import bjc.utils.math.DualExprParser.Result;
+
+public class DualExprParserTest {
+
+	@Test
+	public void testBasics() {
+		assertDEEvalsTo(new Dual(1.0, 0.0), "1");
+	}
+	
+	@Test
+	public void testMath() {
+		assertDEEvalsTo(new Dual(2.0, 0.0), "1 1 +");
+		assertDEEvalsTo(new Dual(-1.0, 0.0), "1 2 -");
+		assertDEEvalsTo(new Dual(4.0, 0.0), "2 2 *");
+		assertDEEvalsTo(new Dual(2.0, 0.0), "4 2 /");
+	}
+	
+	@Test
+	public void testFuncs() {
+		assertDEEvalsTo(new Dual(2.0, -0.0), "-2 abs");
+		
+		
+		assertDEEvalsTo(new Dual(Math.sin(2), -0.0), "2 sin");
+		assertDEEvalsTo(new Dual(Math.cos(2), -0.0), "2 cos");
+		
+		assertDEEvalsTo(new Dual(Math.log(2.0), 0.0), "2 log");
+		assertDEEvalsTo(new Dual(Math.exp(2), 0.0), "2 exp");
+
+		assertDEEvalsTo(new Dual(Math.sqrt(2), 0.0), "2 0.5 pow");
+		assertDEEvalsTo(new Dual(4.0, 0.0), "2 2 pow");
+		
+		assertDEEvalsTo(new Dual(4.0, 0.0), "1 2 + eval 1 +");
+	}
+	
+	@Test
+	public void testVars() {
+		assertDEEvalsTo(new Dual(2.0, 0.0), "x x +", "x", 1);
+		
+		assertDEEvalsTo(new Dual(4.0, 4.0), "x 2 pow", "x", new Dual(2.0, 1.0));
+		assertDEEvalsTo(new Dual(8.0, 12.0), "x 3 pow", "x", new Dual(2.0, 1.0));
+	}
+	
+	@Test(expected = IllegalArgumentException.class)
+	public void testDivZero() {
+		assertDEEvalsTo(new Dual(0.0, 0.0), "1 0 /");
+	}
+	
+	@Test(expected = OperandsRemaining.class)
+	public void testOpsRemaining() {
+		DualExprParser.parseExpression("1 2");
+		
+		assertFalse("Shouldn't reach here", true);
+	}
+	
+	@Test(expected = NonConstantPower.class)
+	public void testNonConstantPower() {
+		DualExprParser.parseExpression("1 1 1 dual pow");
+	}
+	
+	private static void assertDEEvalsTo(Dual res, String inp) {
+		assertDEEvalsTo(false, res, inp);
+	}
+	
+	private static void assertDEEvalsTo(Dual res, String inp, Object... vars) {
+		assertDEEvalsTo(false, res, inp, vars);
+	}
+	
+	private static void assertDEEvalsTo(boolean printExpr, Dual res, String inp, Object... vars) {
+		Map<String, DualExpr> varMap = new HashMap<>();
+		
+		for (int idx = 0; idx < vars.length; idx += 2) {
+			if (!(vars[idx] instanceof String)) {
+				throw new IllegalArgumentException("Expected string for variable name");
+			}
+			
+			String name = (String) vars[idx];
+			
+			DualExpr val;
+			Object tentVal = vars[idx + 1];
+			
+			if (tentVal instanceof Integer) {
+				int vl = (int) tentVal;
+				
+				val = new DualExpr(new Dual(vl));
+			} else if (tentVal instanceof Double) {
+				double vl = (double) tentVal;
+				
+				val = new DualExpr(new Dual(vl));
+			} else if (tentVal instanceof Dual) {
+				val = new DualExpr((Dual) tentVal);
+			} else if (tentVal instanceof DualExpr) {
+				val = (DualExpr) tentVal;
+			} else {
+				throw new IllegalArgumentException("Invalid argument type " + tentVal.getClass().getName());
+			}
+			
+			varMap.put(name, val);
+		}
+		
+		Result res1 = DualExprParser.parseExpression(inp, varMap);
+		
+		DualExpr de1 = res1.expr;
+		
+		if (printExpr) System.out.printf("Expression: '%s'\n", de1);
+		
+		assertEquals(res, de1.evaluate());
+	}
+	
+	private static void assertDEEvalsTo(boolean printExpr, Dual res, String inp) {
+		Result res1 = DualExprParser.parseExpression(inp);
+		
+		DualExpr de1 = res1.expr;
+		
+		if (printExpr) System.out.printf("Expression: '%s'\n", de1);
+		
+		assertEquals(res, de1.evaluate());
+	}
+}
\ No newline at end of file