001/* 002 * Java Genetic Algorithm Library (jenetics-7.2.0). 003 * Copyright (c) 2007-2023 Franz Wilhelmstötter 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 * Author: 018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com) 019 */ 020package io.jenetics.prog.op; 021 022import static java.nio.charset.StandardCharsets.UTF_8; 023import static java.util.Comparator.comparing; 024import static java.util.Objects.requireNonNull; 025import static java.util.stream.Collectors.toCollection; 026import static io.jenetics.ext.internal.util.FormulaParser.TokenType.FUNCTION; 027import static io.jenetics.ext.internal.util.FormulaParser.TokenType.UNARY_OPERATOR; 028import static io.jenetics.internal.util.SerialIO.readInt; 029import static io.jenetics.internal.util.SerialIO.writeInt; 030import static io.jenetics.prog.op.MathTokenType.COMMA; 031import static io.jenetics.prog.op.MathTokenType.DIV; 032import static io.jenetics.prog.op.MathTokenType.IDENTIFIER; 033import static io.jenetics.prog.op.MathTokenType.LPAREN; 034import static io.jenetics.prog.op.MathTokenType.MINUS; 035import static io.jenetics.prog.op.MathTokenType.MOD; 036import static io.jenetics.prog.op.MathTokenType.NUMBER; 037import static io.jenetics.prog.op.MathTokenType.PLUS; 038import static io.jenetics.prog.op.MathTokenType.POW; 039import static io.jenetics.prog.op.MathTokenType.RPAREN; 040import static io.jenetics.prog.op.MathTokenType.TIMES; 041 042import java.io.DataInput; 043import java.io.DataOutput; 044import java.io.IOException; 045import java.io.InvalidObjectException; 046import java.io.ObjectInputStream; 047import java.io.Serial; 048import java.io.Serializable; 049import java.util.TreeSet; 050import java.util.function.Function; 051import java.util.function.Supplier; 052 053import io.jenetics.internal.util.Lazy; 054import io.jenetics.util.ISeq; 055 056import io.jenetics.ext.internal.parser.ParsingException; 057import io.jenetics.ext.internal.parser.Token; 058import io.jenetics.ext.internal.util.FormulaParser; 059import io.jenetics.ext.internal.util.FormulaParser.TokenType; 060import io.jenetics.ext.rewriting.TreeRewriteRule; 061import io.jenetics.ext.rewriting.TreeRewriter; 062import io.jenetics.ext.util.FlatTreeNode; 063import io.jenetics.ext.util.Tree; 064import io.jenetics.ext.util.TreeNode; 065 066/** 067 * Contains methods for parsing mathematical expression. 068 * 069 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 070 * @since 4.1 071 * @version 7.1 072 */ 073public final class MathExpr 074 implements Function<Double[], Double>, Serializable 075{ 076 077 @Serial 078 private static final long serialVersionUID = 1L; 079 080 private static final FormulaParser<Token<String>> FORMULA_PARSER = 081 FormulaParser.<Token<String>>builder() 082 .lparen(t -> t.type() == LPAREN) 083 .rparen(t -> t.type() == RPAREN) 084 .separator(t -> t.type() == COMMA) 085 .unaryOperators(t -> t.type() == PLUS || t.type() == MINUS) 086 .binaryOperators(ops -> ops 087 .add(11, t -> t.type() == PLUS || t.type() == MINUS) 088 .add(12, t -> t.type() == TIMES || t.type() == DIV || t.type() == MOD) 089 .add(13, t -> t.type() == POW) 090 ) 091 .identifiers(t -> t.type() == IDENTIFIER || t.type() == NUMBER) 092 .functions(t -> MathOp.NAMES.contains(t.value())) 093 .build(); 094 095 /** 096 * This tree-rewriter rewrites constant expressions to its single value. 097 * 098 * <pre>{@code 099 * final TreeNode<Op<Double>> tree = MathExpr.parseTree("1 + 2*(6 + 7)"); 100 * MathExpr.CONST_REWRITER.rewrite(tree); 101 * assertEquals(tree.getValue(), Const.of(27.0)); 102 * }</pre> 103 * 104 * @since 5.0 105 */ 106 public static final TreeRewriter<Op<Double>> CONST_REWRITER = 107 ConstRewriter.DOUBLE; 108 109 /** 110 * This rewriter implements some common arithmetic identities, in exactly 111 * this order. 112 * <pre> {@code 113 * sub($x,$x) -> 0 114 * sub($x,0) -> $x 115 * add($x,0) -> $x 116 * add(0,$x) -> $x 117 * add($x,$x) -> mul(2,$x) 118 * div($x,$x) -> 1 119 * div(0,$x) -> 0 120 * mul($x,0) -> 0 121 * mul(0,$x) -> 0 122 * mul($x,1) -> $x 123 * mul(1,$x) -> $x 124 * mul($x,$x) -> pow($x,2) 125 * pow($x,0) -> 1 126 * pow(0,$x) -> 0 127 * pow($x,1) -> $x 128 * pow(1,$x) -> 1 129 * }</pre> 130 * 131 * @since 5.0 132 */ 133 public static final TreeRewriter<Op<Double>> ARITHMETIC_REWRITER = 134 TreeRewriter.concat( 135 compile("sub($x,$x) -> 0"), 136 compile("sub($x,0) -> $x"), 137 compile("add($x,0) -> $x"), 138 compile("add(0,$x) -> $x"), 139 compile("add($x,$x) -> mul(2,$x)"), 140 compile("div($x,$x) -> 1"), 141 compile("div(0,$x) -> 0"), 142 compile("mul($x,0) -> 0"), 143 compile("mul(0,$x) -> 0"), 144 compile("mul($x,1) -> $x"), 145 compile("mul(1,$x) -> $x"), 146 compile("mul($x,$x) -> pow($x,2)"), 147 compile("pow($x,0) -> 1"), 148 compile("pow(0,$x) -> 0"), 149 compile("pow($x,1) -> $x"), 150 compile("pow(1,$x) -> 1") 151 ); 152 153 private static TreeRewriter<Op<Double>> compile(final String rule) { 154 return TreeRewriteRule.parse(rule, MathOp::toMathOp); 155 } 156 157 /** 158 * Combination of the {@link #ARITHMETIC_REWRITER} and the 159 * {@link #CONST_REWRITER}, in this specific order. 160 * 161 * @since 5.0 162 */ 163 public static final TreeRewriter<Op<Double>> REWRITER = TreeRewriter.concat( 164 ARITHMETIC_REWRITER, 165 CONST_REWRITER 166 ); 167 168 private final FlatTreeNode<Op<Double>> _tree; 169 170 private final Lazy<ISeq<Var<Double>>> _vars; 171 172 // Primary constructor. 173 private MathExpr(final FlatTreeNode<Op<Double>> tree) { 174 _tree = requireNonNull(tree); 175 _vars = Lazy.of(() -> ISeq.of( 176 _tree.stream() 177 .filter(node -> node.value() instanceof Var) 178 .map(node -> (Var<Double>)node.value()) 179 .collect(toCollection(() -> new TreeSet<>(comparing(Var::name)))) 180 )); 181 } 182 183 /** 184 * Create a new {@code MathExpr} object from the given operation tree. 185 * 186 * @param tree the underlying operation tree 187 * @throws NullPointerException if the given {@code program} is {@code null} 188 * @throws IllegalArgumentException if the given operation tree is invalid, 189 * which means there is at least one node where the operation arity 190 * and the node child count differ. 191 */ 192 public MathExpr(final Tree<? extends Op<Double>, ?> tree) { 193 this(FlatTreeNode.ofTree(tree)); 194 Program.check(tree); 195 } 196 197 /** 198 * Return the variable list of this <em>math</em> expression. 199 * 200 * @return the variable list of this <em>math</em> expression 201 */ 202 public ISeq<Var<Double>> vars() { 203 return _vars.get(); 204 } 205 206 /** 207 * Return the operation tree underlying {@code this} math expression. 208 * 209 * @since 7.1 210 * 211 * @return the operation tree s 212 */ 213 public Tree<Op<Double>, ?> tree() { 214 return _tree; 215 } 216 217 /** 218 * Return the math expression as an operation tree. 219 * 220 * @return a new expression tree 221 * @deprecated Will be removed, use {@link #tree()} instead 222 */ 223 @Deprecated(forRemoval = true) 224 public TreeNode<Op<Double>> toTree() { 225 return TreeNode.ofTree(_tree); 226 } 227 228 /** 229 * @see #eval(double...) 230 * @see #eval(String, double...) 231 */ 232 @Override 233 public Double apply(final Double[] args) { 234 return Program.eval(_tree, args); 235 } 236 237 /** 238 * Convenient method, which lets you apply the program function without 239 * explicitly create a wrapper array. 240 * 241 * <pre>{@code 242 * final double result = MathExpr.parse("2*z + 3*x - y").eval(3, 2, 1); 243 * assert result == 9.0; 244 * }</pre> 245 * 246 * @see #apply(Double[]) 247 * @see #eval(String, double...) 248 * 249 * @param args the function arguments 250 * @return the evaluated value 251 * @throws NullPointerException if the given variable array is {@code null} 252 * @throws IllegalArgumentException if the length of the argument array 253 * is smaller than the program arity 254 */ 255 public double eval(final double... args) { 256 final double val = apply(box(args)); 257 return val == -0.0 ? 0.0 : val; 258 } 259 260 @Override 261 public int hashCode() { 262 return Tree.hashCode(_tree); 263 } 264 265 @Override 266 public boolean equals(final Object obj) { 267 return obj == this || 268 obj instanceof MathExpr expr && 269 _tree.equals(expr._tree); 270 } 271 272 /** 273 * Return the string representation of this {@code MathExpr} object. The 274 * string returned by this method can be parsed again and will result in the 275 * same expression object. 276 * <pre>{@code 277 * final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5"; 278 * final MathExpr tree = MathExpr.parse(expr); 279 * assert tree.toString().equals(expr); 280 * }</pre> 281 * 282 * @return the expression string 283 */ 284 @Override 285 public String toString() { 286 return format(_tree); 287 } 288 289 /** 290 * Simplifying {@code this} expression by applying the given {@code rewriter} 291 * and the given rewrite {@code limit}. 292 * 293 * @param rewriter the rewriter used for simplifying {@code this} expression 294 * @param limit the rewrite limit 295 * @return a newly created math expression object 296 * @throws NullPointerException if the {@code rewriter} is {@code null} 297 * @throws IllegalArgumentException if the {@code limit} is smaller than 298 * zero 299 */ 300 public MathExpr simplify( 301 final TreeRewriter<Op<Double>> rewriter, 302 final int limit 303 ) { 304 final TreeNode<Op<Double>> tree = TreeNode.ofTree(tree()); 305 rewriter.rewrite(tree, limit); 306 return new MathExpr(FlatTreeNode.ofTree(tree)); 307 } 308 309 /** 310 * Simplifying {@code this} expression by applying the given {@code rewriter}. 311 * 312 * @param rewriter the rewriter used for simplifying {@code this} expression 313 * @return a newly created math expression object 314 * @throws NullPointerException if the {@code rewriter} is {@code null} 315 */ 316 public MathExpr simplify(final TreeRewriter<Op<Double>> rewriter) { 317 return simplify(rewriter, Integer.MAX_VALUE); 318 } 319 320 /** 321 * Simplifies {@code this} expression by applying the default 322 * {@link #REWRITER}. 323 * 324 * @return a newly created math expression object 325 */ 326 public MathExpr simplify() { 327 return simplify(REWRITER); 328 } 329 330 private static Double[] box(final double... values) { 331 final Double[] result = new Double[values.length]; 332 for (int i = values.length; --i >= 0;) { 333 result[i] = values[i]; 334 } 335 return result; 336 } 337 338 private static Op<Double> toOp( 339 final Token<String> token, 340 final TokenType type 341 ) { 342 return switch ((MathTokenType)token.type()) { 343 case PLUS -> type == UNARY_OPERATOR ? MathOp.ID : MathOp.ADD; 344 case MINUS -> type == UNARY_OPERATOR ? MathOp.NEG : MathOp.SUB; 345 case TIMES -> MathOp.MUL; 346 case DIV -> MathOp.DIV; 347 case MOD -> MathOp.MOD; 348 case POW -> MathOp.POW; 349 case NUMBER -> Const.of(Double.parseDouble(token.value())); 350 case IDENTIFIER -> { 351 if (type == FUNCTION) { 352 yield MathOp.toMathOp(token.value()); 353 } else { 354 yield switch (token.value()) { 355 case "π", "PI" -> MathOp.PI; 356 default -> Var.of(token.value()); 357 }; 358 } 359 } 360 default -> throw new ParsingException("Unknown token: " + token); 361 }; 362 } 363 364 365 /* ************************************************************************* 366 * Java object serialization 367 * ************************************************************************/ 368 369 @Serial 370 private Object writeReplace() { 371 return new SerialProxy(SerialProxy.MATH_EXPR, this); 372 } 373 374 @Serial 375 private void readObject(final ObjectInputStream stream) 376 throws InvalidObjectException 377 { 378 throw new InvalidObjectException("Serialization proxy required."); 379 } 380 381 void write(final DataOutput out) throws IOException { 382 final byte[] data = toString().getBytes(UTF_8); 383 writeInt(data.length, out); 384 out.write(data); 385 } 386 387 static MathExpr read(final DataInput in) throws IOException { 388 final byte[] data = new byte[readInt(in)]; 389 in.readFully(data); 390 return parse(new String(data, UTF_8)); 391 } 392 393 /* ************************************************************************* 394 * Static helper methods. 395 * ************************************************************************/ 396 397 /** 398 * Return the string representation of the given {@code tree} object. The 399 * string returned by this method can be parsed again and will result in the 400 * same expression object. 401 * <pre>{@code 402 * final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5"; 403 * final MathExpr tree = MathExpr.parse(expr); 404 * assert MathExpr.format(tree.tree()).equals(expr); 405 * }</pre> 406 * 407 * @since 4.3 408 * 409 * @param tree the tree object to convert to a string 410 * @return a new expression string 411 * @throws NullPointerException if the given {@code tree} is {@code null} 412 */ 413 public static String format(final Tree<? extends Op<Double>, ?> tree) { 414 return MathExprFormatter.format(tree); 415 } 416 417 /** 418 * Parses the given {@code expression} into an AST tree. 419 * 420 * @param expression the expression string 421 * @return the tree representation of the given {@code expression} 422 * @throws NullPointerException if the given {@code expression} is {@code null} 423 * @throws IllegalArgumentException if the given expression is invalid or 424 * can't be parsed. 425 */ 426 public static MathExpr parse(final String expression) { 427 return new MathExpr(FlatTreeNode.ofTree(parseTree(expression))); 428 } 429 430 /** 431 * Parses the given mathematical expression string and returns the 432 * mathematical expression tree. The expression may contain all functions 433 * defined in {@link MathOp}. 434 * <pre>{@code 435 * final Tree<? extends Op<Double>, ?> tree = MathExpr 436 * .parseTree("5 + 6*x + sin(x)^34 + (1 + sin(x*5)/4)/6"); 437 * }</pre> 438 * The example above will lead to the following tree: 439 * <pre> {@code 440 * add 441 * ├── add 442 * │ ├── add 443 * │ │ ├── 5.0 444 * │ │ └── mul 445 * │ │ ├── 6.0 446 * │ │ └── x 447 * │ └── pow 448 * │ ├── sin 449 * │ │ └── x 450 * │ └── 34.0 451 * └── div 452 * ├── add 453 * │ ├── 1.0 454 * │ └── div 455 * │ ├── sin 456 * │ │ └── mul 457 * │ │ ├── x 458 * │ │ └── 5.0 459 * │ └── 4.0 460 * └── 6.0 461 * }</pre> 462 * 463 * @param expression the expression string 464 * @return the parsed expression tree 465 * @throws NullPointerException if the given {@code expression} is {@code null} 466 * @throws IllegalArgumentException if the given expression is invalid or 467 * can't be parsed. 468 */ 469 public static Tree<Op<Double>, ?> parseTree(final String expression) { 470 final var tokenizer = new MathStringTokenizer(expression); 471 return parseTree(tokenizer::next); 472 } 473 474 private static <V> Tree<Op<Double>, ?> 475 parseTree(final Supplier<Token<String>> tokens) { 476 final TreeNode<Op<Double>> tree = FORMULA_PARSER.parse(tokens, MathExpr::toOp); 477 Var.reindex(tree); 478 return FlatTreeNode.ofTree(tree); 479 } 480 481 /** 482 * Evaluates the given {@code expression} with the given arguments. 483 * 484 * <pre>{@code 485 * final double result = MathExpr.eval("2*z + 3*x - y", 3, 2, 1); 486 * assert result == 9.0; 487 * }</pre> 488 * 489 * @see #apply(Double[]) 490 * @see #eval(double...) 491 * 492 * @param expression the expression to evaluate 493 * @param args the expression arguments, in alphabetical order 494 * @return the evaluation result 495 * @throws NullPointerException if the given {@code expression} is 496 * {@code null} 497 * @throws IllegalArgumentException if the given operation tree is invalid, 498 * which means there is at least one node where the operation arity 499 * and the node child count differ. 500 */ 501 public static double eval(final String expression, final double... args) { 502 return parse(expression).eval(args); 503 } 504 505 /** 506 * Evaluates the given {@code expression} with the given arguments. 507 * 508 * @see #apply(Double[]) 509 * @see #eval(double...) 510 * @see #eval(String, double...) 511 * 512 * @since 4.4 513 * 514 * @param expression the expression to evaluate 515 * @param args the expression arguments, in alphabetical order 516 * @return the evaluation result 517 * @throws NullPointerException if the given {@code expression} is 518 * {@code null} 519 */ 520 public static double eval( 521 final Tree<? extends Op<Double>, ?> expression, 522 final double... args 523 ) { 524 return Program.eval(expression, box(args)); 525 } 526 527 /** 528 * Applies the {@link #REWRITER} to the given (mutable) {@code tree}. The 529 * tree rewrite is done in place. 530 * 531 * @see TreeRewriter#rewrite(TreeNode, int) 532 * 533 * @since 5.0 534 * 535 * @param tree the tree to be rewritten 536 * @param limit the maximal number this rewrite rule is applied to the given 537 * tree. This guarantees the termination of the rewrite method. 538 * @return the number of rewrites applied to the input {@code tree} 539 * @throws NullPointerException if the given {@code tree} is {@code null} 540 * @throws IllegalArgumentException if the {@code limit} is smaller than 541 * one 542 */ 543 public static int rewrite(final TreeNode<Op<Double>> tree, final int limit) { 544 return REWRITER.rewrite(tree, limit); 545 } 546 547 /** 548 * Applies the {@link #REWRITER} to the given (mutable) {@code tree}. The 549 * tree rewrite is done in place. The limit of the applied rewrites is set 550 * unlimited ({@link Integer#MAX_VALUE}). 551 * 552 * @see #rewrite(TreeNode, int) 553 * @see TreeRewriter#rewrite(TreeNode) 554 * 555 * @since 5.0 556 * 557 * @param tree the tree to be rewritten 558 * @return {@code true} if the tree has been changed (rewritten) by this 559 * method, {@code false} if the tree hasn't been changed 560 * @throws NullPointerException if the given {@code tree} is {@code null} 561 */ 562 public static int rewrite(final TreeNode<Op<Double>> tree) { 563 return rewrite(tree, Integer.MAX_VALUE); 564 } 565 566}