001 /*
002 * Java Genetic Algorithm Library (jenetics-6.0.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.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 ConstRewriter.DOUBLE;
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.value() instanceof Var)
160 .map(node -> (Var<Double>)node.value())
161 .collect(toCollection(() -> new TreeSet<>(comparing(Var::name))))
162 ));
163 }
164
165 /**
166 * Create a new {@code MathExpr} object from the given operation tree.
167 *
168 * @param tree the underlying operation tree
169 * @throws NullPointerException if the given {@code program} is {@code null}
170 * @throws IllegalArgumentException if the given operation tree is invalid,
171 * which means there is at least one node where the operation arity
172 * and the node child count differ.
173 */
174 public MathExpr(final Tree<? extends Op<Double>, ?> tree) {
175 this(TreeNode.ofTree(tree), true);
176 Program.check(tree);
177 }
178
179 /**
180 * Return the variable list of this <em>math</em> expression.
181 *
182 * @return the variable list of this <em>math</em> expression
183 */
184 public ISeq<Var<Double>> vars() {
185 return _vars.get();
186 }
187
188 /**
189 * Return the math expression as operation tree.
190 *
191 * @return a new expression tree
192 */
193 public TreeNode<Op<Double>> toTree() {
194 return TreeNode.ofTree(_tree);
195 }
196
197 /**
198 * @see #eval(double...)
199 * @see #eval(String, double...)
200 */
201 @Override
202 public Double apply(final Double[] args) {
203 return Program.eval(_tree, args);
204 }
205
206 /**
207 * Convenient method, which lets you apply the program function without
208 * explicitly create a wrapper array.
209 *
210 * <pre>{@code
211 * final double result = MathExpr.parse("2*z + 3*x - y").eval(3, 2, 1);
212 * assert result == 9.0;
213 * }</pre>
214 *
215 * @see #apply(Double[])
216 * @see #eval(String, double...)
217 *
218 * @param args the function arguments
219 * @return the evaluated value
220 * @throws NullPointerException if the given variable array is {@code null}
221 * @throws IllegalArgumentException if the length of the arguments array
222 * is smaller than the program arity
223 */
224 public double eval(final double... args) {
225 final double val = apply(box(args));
226 return val == -0.0 ? 0.0 : val;
227 }
228
229 @Override
230 public int hashCode() {
231 return _tree.hashCode();
232 }
233
234 @Override
235 public boolean equals(final Object obj) {
236 return obj == this ||
237 obj instanceof MathExpr &&
238 Objects.equals(((MathExpr)obj)._tree, _tree);
239 }
240
241 /**
242 * Return the string representation of this {@code MathExpr} object. The
243 * string returned by this method can be parsed again and will result in the
244 * same expression object.
245 * <pre>{@code
246 * final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5";
247 * final MathExpr tree = MathExpr.parse(expr);
248 * assert tree.toString().equals(expr);
249 * }</pre>
250 *
251 * @return the expression string
252 */
253 @Override
254 public String toString() {
255 return format(_tree);
256 }
257
258 /**
259 * Simplifying {@code this} expression by applying the given {@code rewriter}
260 * and the given rewrite {@code limit}.
261 *
262 * @param rewriter the rewriter used for simplifying {@code this} expression
263 * @param limit the rewrite limit
264 * @return a newly created math expression object
265 * @throws NullPointerException if the {@code rewriter} is {@code null}
266 * @throws IllegalArgumentException if the {@code limit} is smaller than
267 * zero
268 */
269 public MathExpr simplify(
270 final TreeRewriter<Op<Double>> rewriter,
271 final int limit
272 ) {
273 final TreeNode<Op<Double>> tree = toTree();
274 rewriter.rewrite(tree, limit);
275 return new MathExpr(tree, true);
276 }
277
278 /**
279 * Simplifying {@code this} expression by applying the given {@code rewriter}.
280 *
281 * @param rewriter the rewriter used for simplifying {@code this} expression
282 * @return a newly created math expression object
283 * @throws NullPointerException if the {@code rewriter} is {@code null}
284 */
285 public MathExpr simplify(final TreeRewriter<Op<Double>> rewriter) {
286 return simplify(rewriter, Integer.MAX_VALUE);
287 }
288
289 /**
290 * Simplifies {@code this} expression by applying the default
291 * {@link #REWRITER}.
292 *
293 * @return a newly created math expression object
294 */
295 public MathExpr simplify() {
296 return simplify(REWRITER);
297 }
298
299
300 /* *************************************************************************
301 * Java object serialization
302 * ************************************************************************/
303
304 private Object writeReplace() {
305 return new Serial(Serial.MATH_EXPR, this);
306 }
307
308 private void readObject(final ObjectInputStream stream)
309 throws InvalidObjectException
310 {
311 throw new InvalidObjectException("Serialization proxy required.");
312 }
313
314 void write(final DataOutput out) throws IOException {
315 final byte[] data = toString().getBytes(UTF_8);
316 writeInt(data.length, out);
317 out.write(data);
318 }
319
320 static MathExpr read(final DataInput in) throws IOException {
321 final byte[] data = new byte[readInt(in)];
322 in.readFully(data);
323 return parse(new String(data, UTF_8));
324 }
325
326
327 /* *************************************************************************
328 * Static helper methods.
329 * ************************************************************************/
330
331 /**
332 * Return the string representation of the given {@code tree} object. The
333 * string returned by this method can be parsed again and will result in the
334 * same expression object.
335 * <pre>{@code
336 * final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5";
337 * final MathExpr tree = MathExpr.parse(expr);
338 * assert MathExpr.format(tree.tree()).equals(expr);
339 * }</pre>
340 *
341 * @since 4.3
342 *
343 * @param tree the tree object to convert to a string
344 * @return a new expression string
345 * @throws NullPointerException if the given {@code tree} is {@code null}
346 */
347 public static String format(final Tree<? extends Op<Double>, ?> tree) {
348 return MathExprFormatter.format(tree);
349 }
350
351 /**
352 * Parses the given {@code expression} into a AST tree.
353 *
354 * @param expression the expression string
355 * @return the tree representation of the given {@code expression}
356 * @throws NullPointerException if the given {@code expression} is {@code null}
357 * @throws IllegalArgumentException if the given expression is invalid or
358 * can't be parsed.
359 */
360 public static MathExpr parse(final String expression) {
361 final Tree<? extends Op<Double>, ?> tree = parseTree(expression);
362 Program.check(tree);
363 return new MathExpr(tree, true);
364 }
365
366 /**
367 * Parses the given mathematical expression string and returns the
368 * mathematical expression tree. The expression may contain all functions
369 * defined in {@link MathOp}.
370 * <pre>{@code
371 * final Tree<? extends Op<Double>, ?> tree = MathExpr
372 * .parseTree("5 + 6*x + sin(x)^34 + (1 + sin(x*5)/4)/6");
373 * }</pre>
374 * The example above will lead to the following tree:
375 * <pre> {@code
376 * add
377 * ├── add
378 * │ ├── add
379 * │ │ ├── 5.0
380 * │ │ └── mul
381 * │ │ ├── 6.0
382 * │ │ └── x
383 * │ └── pow
384 * │ ├── sin
385 * │ │ └── x
386 * │ └── 34.0
387 * └── div
388 * ├── add
389 * │ ├── 1.0
390 * │ └── div
391 * │ ├── sin
392 * │ │ └── mul
393 * │ │ ├── x
394 * │ │ └── 5.0
395 * │ └── 4.0
396 * └── 6.0
397 * }</pre>
398 *
399 * @param expression the expression string
400 * @return the parsed expression tree
401 * @throws NullPointerException if the given {@code expression} is {@code null}
402 * @throws IllegalArgumentException if the given expression is invalid or
403 * can't be parsed.
404 */
405 public static TreeNode<Op<Double>> parseTree(final String expression) {
406 return MathExprParser.parse(expression);
407 }
408
409 /**
410 * Evaluates the given {@code expression} with the given arguments.
411 *
412 * <pre>{@code
413 * final double result = MathExpr.eval("2*z + 3*x - y", 3, 2, 1);
414 * assert result == 9.0;
415 * }</pre>
416 *
417 * @see #apply(Double[])
418 * @see #eval(double...)
419 *
420 * @param expression the expression to evaluate
421 * @param args the expression arguments, in alphabetical order
422 * @return the evaluation result
423 * @throws NullPointerException if the given {@code expression} is
424 * {@code null}
425 * @throws IllegalArgumentException if the given operation tree is invalid,
426 * which means there is at least one node where the operation arity
427 * and the node child count differ.
428 */
429 public static double eval(final String expression, final double... args) {
430 return parse(expression).eval(args);
431 }
432
433 /**
434 * Evaluates the given {@code expression} with the given arguments.
435 *
436 * @see #apply(Double[])
437 * @see #eval(double...)
438 * @see #eval(String, double...)
439 *
440 * @since 4.4
441 *
442 * @param expression the expression to evaluate
443 * @param args the expression arguments, in alphabetical order
444 * @return the evaluation result
445 * @throws NullPointerException if the given {@code expression} is
446 * {@code null}
447 */
448 public static double eval(
449 final Tree<? extends Op<Double>, ?> expression,
450 final double... args
451 ) {
452 return new MathExpr(expression, true).eval(args);
453 }
454
455 /**
456 * Applies the {@link #REWRITER} to the given (mutable) {@code tree}. The
457 * tree rewrite is done in place.
458 *
459 * @see TreeRewriter#rewrite(TreeNode, int)
460 *
461 * @since 5.0
462 *
463 * @param tree the tree to be rewritten
464 * @param limit the maximal number this rewrite rule is applied to the given
465 * tree. This guarantees the termination of the rewrite method.
466 * @return the number of rewrites applied to the input {@code tree}
467 * @throws NullPointerException if the given {@code tree} is {@code null}
468 * @throws IllegalArgumentException if the {@code limit} is smaller than
469 * one
470 */
471 public static int rewrite(final TreeNode<Op<Double>> tree, final int limit) {
472 return REWRITER.rewrite(tree, limit);
473 }
474
475 /**
476 * Applies the {@link #REWRITER} to the given (mutable) {@code tree}. The
477 * tree rewrite is done in place. The limit of the applied rewrites is set
478 * unlimited ({@link Integer#MAX_VALUE}).
479 *
480 * @see #rewrite(TreeNode, int)
481 * @see TreeRewriter#rewrite(TreeNode)
482 *
483 * @since 5.0
484 *
485 * @param tree the tree to be rewritten
486 * @return {@code true} if the tree has been changed (rewritten) by this
487 * method, {@code false} if the tree hasn't been changed
488 * @throws NullPointerException if the given {@code tree} is {@code null}
489 */
490 public static int rewrite(final TreeNode<Op<Double>> tree) {
491 return rewrite(tree, Integer.MAX_VALUE);
492 }
493
494 }
|