001 /*
002 * Java Genetic Algorithm Library (jenetics-5.1.0).
003 * Copyright (c) 2007-2019 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 */
020 package io.jenetics.prog.op;
021
022 import static java.nio.charset.StandardCharsets.UTF_8;
023 import static java.util.Objects.requireNonNull;
024 import static io.jenetics.internal.util.SerialIO.readInt;
025 import static io.jenetics.internal.util.SerialIO.writeInt;
026
027 import java.io.DataInput;
028 import java.io.DataOutput;
029 import java.io.IOException;
030 import java.io.InvalidObjectException;
031 import java.io.ObjectInputStream;
032 import java.io.Serializable;
033 import java.util.Comparator;
034 import java.util.Objects;
035 import java.util.TreeSet;
036 import java.util.function.Function;
037 import java.util.stream.Collectors;
038 import java.util.stream.DoubleStream;
039
040 import io.jenetics.internal.util.Lazy;
041 import io.jenetics.util.ISeq;
042
043 import io.jenetics.ext.rewriting.TreeRewriteRule;
044 import io.jenetics.ext.rewriting.TreeRewriter;
045 import io.jenetics.ext.util.Tree;
046 import io.jenetics.ext.util.TreeNode;
047
048 /**
049 * This class allows you to create a math operation tree from an expression
050 * string. The expression string may only contain functions/operations defined
051 * in {@link MathOp}.
052 *
053 * <pre>{@code
054 * final MathExpr expr = MathExpr.parse("5 + 6*x + sin(x)^34 + (1 + sin(x*5)/4)/6");
055 * final double result = expr.eval(4.32);
056 * assert result == 31.170600453465315;
057 *
058 * assert 12.0 == MathExpr.eval("3*4");
059 * assert 24.0 == MathExpr.eval("3*4*x", 2);
060 * assert 28.0 == MathExpr.eval("3*4*x + y", 2, 4);
061 * }</pre>
062 *
063 * @see MathOp
064 *
065 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
066 * @version 5.0
067 * @since 4.1
068 */
069 public final class MathExpr
070 implements
071 Function<Double[], Double>,
072 Serializable
073 {
074
075 private static final long serialVersionUID = 1L;
076
077 /**
078 * This tree-rewriter rewrites constant expressions to its single value.
079 *
080 * <pre>{@code
081 * final TreeNode<Op<Double>> tree = MathExpr.parseTree("1 + 2*(6 + 7)");
082 * MathExpr.CONST_REWRITER.rewrite(tree);
083 * assertEquals(tree.getValue(), Const.of(27.0));
084 * }</pre>
085 *
086 * @since 5.0
087 */
088 public static final TreeRewriter<Op<Double>> CONST_REWRITER =
089 new ConstExprRewriter();
090
091 /**
092 * This rewriter implements some common arithmetic identities, in exactly
093 * this order.
094 * <pre> {@code
095 * sub($x,$x) -> 0
096 * sub($x,0) -> $x
097 * add($x,0) -> $x
098 * add(0,$x) -> $x
099 * add($x,$x) -> mul(2,$x)
100 * div($x,$x) -> 1
101 * div(0,$x) -> 0
102 * mul($x,0) -> 0
103 * mul(0,$x) -> 0
104 * mul($x,1) -> $x
105 * mul(1,$x) -> $x
106 * mul($x,$x) -> pow($x,2)
107 * pow($x,0) -> 1
108 * pow(0,$x) -> 0
109 * pow($x,1) -> $x
110 * pow(1,$x) -> 1
111 * }</pre>
112 *
113 * @since 5.0
114 */
115 public static final TreeRewriter<Op<Double>> ARITHMETIC_REWRITER =
116 TreeRewriter.concat(
117 compile("sub($x,$x) -> 0"),
118 compile("sub($x,0) -> $x"),
119 compile("add($x,0) -> $x"),
120 compile("add(0,$x) -> $x"),
121 compile("add($x,$x) -> mul(2,$x)"),
122 compile("div($x,$x) -> 1"),
123 compile("div(0,$x) -> 0"),
124 compile("mul($x,0) -> 0"),
125 compile("mul(0,$x) -> 0"),
126 compile("mul($x,1) -> $x"),
127 compile("mul(1,$x) -> $x"),
128 compile("mul($x,$x) -> pow($x,2)"),
129 compile("pow($x,0) -> 1"),
130 compile("pow(0,$x) -> 0"),
131 compile("pow($x,1) -> $x"),
132 compile("pow(1,$x) -> 1")
133 );
134
135 private static TreeRewriter<Op<Double>> compile(final String rule) {
136 return TreeRewriteRule.parse(rule, MathOp::toMathOp);
137 }
138
139 /**
140 * Combination of the {@link #ARITHMETIC_REWRITER} and the
141 * {@link #CONST_REWRITER}, in this specific order.
142 *
143 * @since 5.0
144 */
145 public static final TreeRewriter<Op<Double>> REWRITER = TreeRewriter.concat(
146 ARITHMETIC_REWRITER,
147 CONST_REWRITER
148 );
149
150 private final Tree<? extends Op<Double>, ?> _tree;
151
152 private final Lazy<ISeq<Var<Double>>> _vars;
153
154 // Primary constructor.
155 private MathExpr(final Tree<? extends Op<Double>, ?> tree, boolean primary) {
156 _tree = requireNonNull(tree);
157 _vars = Lazy.of(() -> ISeq.of(
158 _tree.stream()
159 .filter(node -> node.getValue() instanceof Var)
160 .map(node -> (Var<Double>)node.getValue())
161 .collect(Collectors.toCollection(() ->
162 new TreeSet<>(Comparator.comparing(Var::name))))
163 ));
164 }
165
166 /**
167 * Create a new {@code MathExpr} object from the given operation tree.
168 *
169 * @param tree the underlying operation tree
170 * @throws NullPointerException if the given {@code program} is {@code null}
171 * @throws IllegalArgumentException if the given operation tree is invalid,
172 * which means there is at least one node where the operation arity
173 * and the node child count differ.
174 */
175 public MathExpr(final Tree<? extends Op<Double>, ?> tree) {
176 this(TreeNode.ofTree(tree), true);
177 Program.check(tree);
178 }
179
180 /**
181 * Return the variable list of this <em>math</em> expression.
182 *
183 * @return the variable list of this <em>math</em> expression
184 */
185 public ISeq<Var<Double>> vars() {
186 return _vars.get();
187 }
188
189 /**
190 * Return the math expression as operation tree.
191 *
192 * @return a new expression tree
193 */
194 public TreeNode<Op<Double>> toTree() {
195 return TreeNode.ofTree(_tree);
196 }
197
198 /**
199 * @see #eval(double...)
200 * @see #eval(String, double...)
201 */
202 @Override
203 public Double apply(final Double[] args) {
204 return Program.eval(_tree, args);
205 }
206
207 /**
208 * Convenient method, which lets you apply the program function without
209 * explicitly create a wrapper array.
210 *
211 * <pre>{@code
212 * final double result = MathExpr.parse("2*z + 3*x - y").eval(3, 2, 1);
213 * assert result == 9.0;
214 * }</pre>
215 *
216 * @see #apply(Double[])
217 * @see #eval(String, double...)
218 *
219 * @param args the function arguments
220 * @return the evaluated value
221 * @throws NullPointerException if the given variable array is {@code null}
222 * @throws IllegalArgumentException if the length of the arguments array
223 * is smaller than the program arity
224 */
225 public double eval(final double... args) {
226 final double val = apply(
227 DoubleStream.of(args)
228 .boxed()
229 .toArray(Double[]::new)
230 );
231 return val == -0.0 ? 0.0 : val;
232 }
233
234 @Override
235 public int hashCode() {
236 return _tree.hashCode();
237 }
238
239 @Override
240 public boolean equals(final Object obj) {
241 return obj == this ||
242 obj instanceof MathExpr &&
243 Objects.equals(((MathExpr)obj)._tree, _tree);
244 }
245
246 /**
247 * Return the string representation of this {@code MathExpr} object. The
248 * string returned by this method can be parsed again and will result in the
249 * same expression object.
250 * <pre>{@code
251 * final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5";
252 * final MathExpr tree = MathExpr.parse(expr);
253 * assert tree.toString().equals(expr);
254 * }</pre>
255 *
256 * @return the expression string
257 */
258 @Override
259 public String toString() {
260 return format(_tree);
261 }
262
263 /**
264 * Simplifying {@code this} expression by applying the given {@code rewriter}
265 * and the given rewrite {@code limit}.
266 *
267 * @param rewriter the rewriter used for simplifying {@code this} expression
268 * @param limit the rewrite limit
269 * @return a newly created math expression object
270 * @throws NullPointerException if the {@code rewriter} is {@code null}
271 * @throws IllegalArgumentException if the {@code limit} is smaller than
272 * zero
273 */
274 public MathExpr simplify(
275 final TreeRewriter<Op<Double>> rewriter,
276 final int limit
277 ) {
278 final TreeNode<Op<Double>> tree = toTree();
279 rewriter.rewrite(tree, limit);
280 return new MathExpr(tree, true);
281 }
282
283 /**
284 * Simplifying {@code this} expression by applying the given {@code rewriter}.
285 *
286 * @param rewriter the rewriter used for simplifying {@code this} expression
287 * @return a newly created math expression object
288 * @throws NullPointerException if the {@code rewriter} is {@code null}
289 */
290 public MathExpr simplify(final TreeRewriter<Op<Double>> rewriter) {
291 return simplify(rewriter, Integer.MAX_VALUE);
292 }
293
294 /**
295 * Simplifies {@code this} expression by applying the default
296 * {@link #REWRITER}.
297 *
298 * @return a newly created math expression object
299 */
300 public MathExpr simplify() {
301 return simplify(REWRITER);
302 }
303
304
305 /* *************************************************************************
306 * Java object serialization
307 * ************************************************************************/
308
309 private Object writeReplace() {
310 return new Serial(Serial.MATH_EXPR, this);
311 }
312
313 private void readObject(final ObjectInputStream stream)
314 throws InvalidObjectException
315 {
316 throw new InvalidObjectException("Serialization proxy required.");
317 }
318
319 void write(final DataOutput out) throws IOException {
320 final byte[] data = toString().getBytes(UTF_8);
321 writeInt(data.length, out);
322 out.write(data);
323 }
324
325 static MathExpr read(final DataInput in) throws IOException {
326 final byte[] data = new byte[readInt(in)];
327 in.readFully(data);
328 return parse(new String(data, UTF_8));
329 }
330
331
332 /* *************************************************************************
333 * Static helper methods.
334 * ************************************************************************/
335
336 /**
337 * Return the string representation of the given {@code tree} object. The
338 * string returned by this method can be parsed again and will result in the
339 * same expression object.
340 * <pre>{@code
341 * final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5";
342 * final MathExpr tree = MathExpr.parse(expr);
343 * assert MathExpr.format(tree.tree()).equals(expr);
344 * }</pre>
345 *
346 * @since 4.3
347 *
348 * @param tree the tree object to convert to a string
349 * @return a new expression string
350 * @throws NullPointerException if the given {@code tree} is {@code null}
351 */
352 public static String format(final Tree<? extends Op<Double>, ?> tree) {
353 return MathExprFormatter.format(tree);
354 }
355
356 /**
357 * Parses the given {@code expression} into a AST tree.
358 *
359 * @param expression the expression string
360 * @return the tree representation of the given {@code expression}
361 * @throws NullPointerException if the given {@code expression} is {@code null}
362 * @throws IllegalArgumentException if the given expression is invalid or
363 * can't be parsed.
364 */
365 public static MathExpr parse(final String expression) {
366 final Tree<? extends Op<Double>, ?> tree = parseTree(expression);
367 Program.check(tree);
368 return new MathExpr(tree, true);
369 }
370
371 /**
372 * Parses the given mathematical expression string and returns the
373 * mathematical expression tree. The expression may contain all functions
374 * defined in {@link MathOp}.
375 * <pre>{@code
376 * final Tree<? extends Op<Double>, ?> tree = MathExpr
377 * .parseTree("5 + 6*x + sin(x)^34 + (1 + sin(x*5)/4)/6");
378 * }</pre>
379 * The example above will lead to the following tree:
380 * <pre> {@code
381 * add
382 * ├── add
383 * │ ├── add
384 * │ │ ├── 5.0
385 * │ │ └── mul
386 * │ │ ├── 6.0
387 * │ │ └── x
388 * │ └── pow
389 * │ ├── sin
390 * │ │ └── x
391 * │ └── 34.0
392 * └── div
393 * ├── add
394 * │ ├── 1.0
395 * │ └── div
396 * │ ├── sin
397 * │ │ └── mul
398 * │ │ ├── x
399 * │ │ └── 5.0
400 * │ └── 4.0
401 * └── 6.0
402 * }</pre>
403 *
404 * @param expression the expression string
405 * @return the parsed expression tree
406 * @throws NullPointerException if the given {@code expression} is {@code null}
407 * @throws IllegalArgumentException if the given expression is invalid or
408 * can't be parsed.
409 */
410 public static TreeNode<Op<Double>> parseTree(final String expression) {
411 return MathExprParser.parse(expression);
412 }
413
414 /**
415 * Evaluates the given {@code expression} with the given arguments.
416 *
417 * <pre>{@code
418 * final double result = MathExpr.eval("2*z + 3*x - y", 3, 2, 1);
419 * assert result == 9.0;
420 * }</pre>
421 *
422 * @see #apply(Double[])
423 * @see #eval(double...)
424 *
425 * @param expression the expression to evaluate
426 * @param args the expression arguments, in alphabetical order
427 * @return the evaluation result
428 * @throws NullPointerException if the given {@code expression} is
429 * {@code null}
430 * @throws IllegalArgumentException if the given operation tree is invalid,
431 * which means there is at least one node where the operation arity
432 * and the node child count differ.
433 */
434 public static double eval(final String expression, final double... args) {
435 return parse(expression).eval(args);
436 }
437
438 /**
439 * Evaluates the given {@code expression} with the given arguments.
440 *
441 * @see #apply(Double[])
442 * @see #eval(double...)
443 * @see #eval(String, double...)
444 *
445 * @since 4.4
446 *
447 * @param expression the expression to evaluate
448 * @param args the expression arguments, in alphabetical order
449 * @return the evaluation result
450 * @throws NullPointerException if the given {@code expression} is
451 * {@code null}
452 */
453 public static double eval(
454 final Tree<? extends Op<Double>, ?> expression,
455 final double... args
456 ) {
457 return new MathExpr(expression, true).eval(args);
458 }
459
460 /**
461 * Applies the {@link #REWRITER} to the given (mutable) {@code tree}. The
462 * tree rewrite is done in place.
463 *
464 * @see TreeRewriter#rewrite(TreeNode, int)
465 *
466 * @since 5.0
467 *
468 * @param tree the tree to be rewritten
469 * @param limit the maximal number this rewrite rule is applied to the given
470 * tree. This guarantees the termination of the rewrite method.
471 * @return the number of rewrites applied to the input {@code tree}
472 * @throws NullPointerException if the given {@code tree} is {@code null}
473 * @throws IllegalArgumentException if the {@code limit} is smaller than
474 * one
475 */
476 public static int rewrite(final TreeNode<Op<Double>> tree, final int limit) {
477 return REWRITER.rewrite(tree, limit);
478 }
479
480 /**
481 * Applies the {@link #REWRITER} to the given (mutable) {@code tree}. The
482 * tree rewrite is done in place. The limit of the applied rewrites is set
483 * unlimited ({@link Integer#MAX_VALUE}).
484 *
485 * @see #rewrite(TreeNode, int)
486 * @see TreeRewriter#rewrite(TreeNode)
487 *
488 * @since 5.0
489 *
490 * @param tree the tree to be rewritten
491 * @return {@code true} if the tree has been changed (rewritten) by this
492 * method, {@code false} if the tree hasn't been changed
493 * @throws NullPointerException if the given {@code tree} is {@code null}
494 */
495 public static int rewrite(final TreeNode<Op<Double>> tree) {
496 return rewrite(tree, Integer.MAX_VALUE);
497 }
498
499 }
|