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