MathExpr.java
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 outthrows 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 inthrows 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 }