MathExpr.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-4.2.0).
003  * Copyright (c) 2007-2018 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.util.Objects.requireNonNull;
023 
024 import java.io.DataInput;
025 import java.io.DataOutput;
026 import java.io.IOException;
027 import java.io.InvalidObjectException;
028 import java.io.ObjectInputStream;
029 import java.io.Serializable;
030 import java.util.Comparator;
031 import java.util.EnumMap;
032 import java.util.Map;
033 import java.util.Objects;
034 import java.util.TreeSet;
035 import java.util.function.Function;
036 import java.util.stream.Collectors;
037 import java.util.stream.DoubleStream;
038 
039 import io.jenetics.util.ISeq;
040 
041 import io.jenetics.ext.util.Tree;
042 import io.jenetics.ext.util.TreeNode;
043 
044 /**
045  * This class allows you to create a math operation tree from an expression
046  * string. The expression string may only contain functions/operations defined
047  * in {@link MathOp}.
048  *
049  <pre>{@code
050  * final MathExpr expr = MathExpr.parse("5 + 6*x + sin(x)^34 + (1 + sin(x*5)/4)/6");
051  * final double result = expr.eval(4.32);
052  * assert result == 31.170600453465315;
053  *
054  * assert 12.0 == MathExpr.eval("3*4");
055  * assert 24.0 == MathExpr.eval("3*4*x", 2);
056  * assert 28.0 == MathExpr.eval("3*4*x + y", 2, 4);
057  * }</pre>
058  *
059  @see MathOp
060  *
061  @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
062  @version 4.1
063  @since 4.1
064  */
065 public final class MathExpr
066     implements
067         Function<Double[], Double>,
068         Serializable
069 {
070 
071     private static final long serialVersionUID = 1L;
072 
073     private static final Map<MathOp, String> INFIX_OPS = new EnumMap<>(MathOp.class);
074     static {
075         INFIX_OPS.put(MathOp.ADD, " + ");
076         INFIX_OPS.put(MathOp.SUB, " - ");
077         INFIX_OPS.put(MathOp.MUL, "*");
078         INFIX_OPS.put(MathOp.DIV, "/");
079         INFIX_OPS.put(MathOp.MOD, "%");
080         INFIX_OPS.put(MathOp.POW, "^");
081     }
082 
083     private final Tree<? extends Op<Double>, ?> _tree;
084 
085     // Primary constructor.
086     private MathExpr(final Tree<? extends Op<Double>, ?> tree, boolean primary) {
087         _tree = requireNonNull(tree);
088     }
089 
090     /**
091      * Create a new {@code MathExpr} object from the given operation tree.
092      *
093      @param tree the underlying operation tree
094      @throws NullPointerException if the given {@code program} is {@code null}
095      @throws IllegalArgumentException if the given operation tree is invalid,
096      *         which means there is at least one node where the operation arity
097      *         and the node child count differ.
098      */
099     public MathExpr(final Tree<? extends Op<Double>, ?> tree) {
100         this(TreeNode.ofTree(tree)true);
101         Program.check(tree);
102     }
103 
104     /**
105      * Return the variable list of this <em>math</em> expression.
106      *
107      @return the variable list of this <em>math</em> expression
108      */
109     public ISeq<Var<Double>> vars() {
110         return ISeq.of(
111             _tree.stream()
112                 .filter(node -> node.getValue() instanceof Var)
113                 .map(node -> (Var<Double>)node.getValue())
114                 .collect(Collectors.toCollection(() ->
115                     new TreeSet<>(Comparator.comparing(Var::name))))
116         );
117     }
118 
119     /**
120      * Return the math expression as operation tree.
121      *
122      @return a new expression tree
123      */
124     public Tree<? extends Op<Double>, ?> toTree() {
125         return TreeNode.ofTree(_tree);
126     }
127 
128     /**
129      @see #eval(double...)
130      @see #eval(String, double...)
131      */
132     @Override
133     public Double apply(final Double[] args) {
134         return Program.eval(_tree, args);
135     }
136 
137     /**
138      * Convenient method, which lets you apply the program function without
139      * explicitly create a wrapper array.
140      *
141      <pre>{@code
142      *  final double result = MathExpr.parse("2*z + 3*x - y").eval(3, 2, 1);
143      *  assert result == 9.0;
144      * }</pre>
145      *
146      @see #apply(Double[])
147      @see #eval(String, double...)
148      *
149      @param args the function arguments
150      @return the evaluated value
151      @throws NullPointerException if the given variable array is {@code null}
152      @throws IllegalArgumentException if the length of the arguments array
153      *         is smaller than the program arity
154      */
155     public double eval(final double... args) {
156         return apply(DoubleStream.of(args).boxed().toArray(Double[]::new));
157     }
158 
159     @Override
160     public int hashCode() {
161         return _tree.hashCode();
162     }
163 
164     @Override
165     public boolean equals(final Object obj) {
166         return obj == this ||
167             obj instanceof MathExpr &&
168             Objects.equals(((MathExprobj)._tree, _tree);
169     }
170 
171     /**
172      * Return the string representation of this {@code MathExpr} object. The
173      * string returned by this method can be parsed again and will result in the
174      * same expression object.
175      <pre>{@code
176      *  final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5";
177      *  final MathExpr tree = MathExpr.parse(expr);
178      *  assert tree.toString().equals(expr);
179      * }</pre>
180      *
181      @return the expression string
182      */
183     @Override
184     public String toString() {
185         return toString(_tree);
186     }
187 
188     private static String toString(
189         final Tree<? extends Op<Double>, ?> tree,
190         final StringBuilder out
191     ) {
192         final Op<Double> op = tree.getValue();
193         if (INFIX_OPS.containsKey(op)) {
194             infix(INFIX_OPS.get(op), tree, out);
195         else {
196             out.append(op);
197             if (!tree.isLeaf()) {
198                 final boolean brackets = true;
199 
200                 if (bracketsout.append("(");
201                 toString(tree.getChild(0), out);
202                 for (int i = 1; i < tree.childCount(); ++i) {
203                     out.append(", ");
204                     toString(tree.getChild(i), out);
205                 }
206                 if (bracketsout.append(")");
207             }
208         }
209 
210         return out.toString();
211     }
212 
213     private static void infix(
214         final String op,
215         final Tree<? extends Op<Double>, ?> tree,
216         final StringBuilder out
217     ) {
218         final boolean brackets = true;
219 
220         if (bracketsout.append("(");
221         toString(tree.getChild(0), out);
222         out.append(op);
223         toString(tree.getChild(1), out);
224         if (bracketsout.append(")");
225     }
226 
227     /**
228      * Tries to simplify {@code this} math expression.
229      *
230      <pre>{@code
231      * final MathExpr expr = MathExpr.parse("4.0 + 4.0 + x*(5.0 + 13.0)");
232      * final MathExpr simplified = expr.simplify()
233      * System.out.println(simplified);
234      * }</pre>
235      * The simplified expression will be look like this: {@code 8.0 + (x*18.0)}.
236      *
237      @see #prune(TreeNode)
238      @see #simplify(Tree)
239      *
240      @return a new simplified math expression
241      */
242     public MathExpr simplify() {
243         return new MathExpr(simplify(_tree));
244     }
245 
246 
247     /* *************************************************************************
248      *  Java object serialization
249      * ************************************************************************/
250 
251     private Object writeReplace() {
252         return new Serial(Serial.MATH_EXPR, this);
253     }
254 
255     private void readObject(final ObjectInputStream stream)
256         throws InvalidObjectException
257     {
258         throw new InvalidObjectException("Serialization proxy required.");
259     }
260 
261     void write(final DataOutput outthrows IOException {
262         final byte[] data = toString().getBytes("UTF-8");
263         out.writeInt(data.length);
264         out.write(data);
265     }
266 
267     static MathExpr read(final DataInput inthrows IOException {
268         final byte[] data = new byte[in.readInt()];
269         in.readFully(data);
270         return parse(new String(data, "UTF-8"));
271     }
272 
273 
274     /* *************************************************************************
275      * Static helper methods.
276      * ************************************************************************/
277 
278     /**
279      * Return the string representation of the given {@code tree} object. The
280      * string returned by this method can be parsed again and will result in the
281      * same expression object.
282      <pre>{@code
283      *  final String expr = "5.0 + 6.0*x + sin(x)^34.0 + (1.0 + sin(x*5.0)/4.0) + 6.5";
284      *  final MathExpr tree = MathExpr.parse(expr);
285      *  assert MathExpr.toString(tree.tree()).equals(expr);
286      * }</pre>
287      *
288      @param tree the tree object to convert to a string
289      @return a new expression string
290      @throws NullPointerException if the given {@code tree} is {@code null}
291      */
292     public static String toString(final Tree<? extends Op<Double>, ?> tree) {
293         return toString(tree, new StringBuilder());
294     }
295 
296     /**
297      * Parses the given {@code expression} into a AST tree.
298      *
299      @param expression the expression string
300      @return the tree representation of the given {@code expression}
301      */
302     public static MathExpr parse(final String expression) {
303         final Tree<? extends Op<Double>, ?> tree = parseTree(expression);
304         Program.check(tree);
305         return new MathExpr(tree, true);
306     }
307 
308     /**
309      * Parses the given mathematical expression string and returns the
310      * mathematical expression tree. The expression may contain all functions
311      * defined in {@link MathOp}.
312      <pre>{@code
313      * final TreeNode<Op<Double>> tree = MathExpr
314      *     .parseTree("5 + 6*x + sin(x)^34 + (1 + sin(x*5)/4)/6");
315      * }</pre>
316      * The example above will lead to the following tree:
317      <pre> {@code
318      *  add
319      *  ├── add
320      *  │   ├── add
321      *  │   │   ├── 5.0
322      *  │   │   └── mul
323      *  │   │       ├── 6.0
324      *  │   │       └── x
325      *  │   └── pow
326      *  │       ├── sin
327      *  │       │   └── x
328      *  │       └── 34.0
329      *  └── div
330      *      ├── add
331      *      │   ├── 1.0
332      *      │   └── div
333      *      │       ├── sin
334      *      │       │   └── mul
335      *      │       │       ├── x
336      *      │       │       └── 5.0
337      *      │       └── 4.0
338      *      └── 6.0
339      * }</pre>
340      *
341      @param expression the expression string
342      @return the parsed expression tree
343      @throws NullPointerException if the given {@code expression} is {@code null}
344      @throws IllegalArgumentException if the given expression is invalid or
345      *         can't be parsed.
346      */
347     public static Tree<? extends Op<Double>, ?>
348     parseTree(final String expression) {
349         return MathExprParser.parse(expression);
350     }
351 
352     /**
353      * Evaluates the given {@code expression} with the given arguments.
354      *
355      <pre>{@code
356      *  final double result = MathExpr.eval("2*z + 3*x - y", 3, 2, 1);
357      *  assert result == 9.0;
358      * }</pre>
359      *
360      @see #apply(Double[])
361      @see #eval(double...)
362      *
363      @param expression the expression to evaluate
364      @param args the expression arguments, in alphabetical order
365      @return the evaluation result
366      @throws NullPointerException if the given {@code program} is {@code null}
367      @throws IllegalArgumentException if the given operation tree is invalid,
368      *         which means there is at least one node where the operation arity
369      *         and the node child count differ.
370      */
371     public static double eval(final String expression, final double... args) {
372         return parse(expression).eval(args);
373     }
374 
375     /**
376      * Tries to simplify the given math tree.
377      *
378      <pre>{@code
379      * final Tree<? extends Op<Double>, ?> tree =
380      *     MathExpr.parseTree("4.0 + 4.0 + x*(5.0 + 13.0)");
381      * final Tree<? extends Op<Double>, ?> simplified = MathExpr.simplify(tree)
382      * System.out.println(simplified);
383      * }</pre>
384      * The simplified tree will be look like this:
385      <pre> {@code
386      *  add
387      *  ├── 8.0
388      *  └── mul
389      *      ├── x
390      *      └── 18.0
391      * }</pre>
392      *
393      @see #prune(TreeNode)
394      @see #simplify()
395      *
396      @param tree the math tree to simplify
397      @return the new simplified tree
398      @throws NullPointerException if the given {@code tree} is {@code null}
399      */
400     public static Tree<? extends Op<Double>, ?>
401     simplify(final Tree<? extends Op<Double>, ?> tree) {
402         return MathExprSimplifier.prune(TreeNode.ofTree(tree));
403     }
404 
405     /**
406      * Tries to simplify the given math tree in place.
407      *
408      @see #simplify(Tree)
409      @see #simplify()
410      *
411      @param tree the math tree to simplify
412      @throws NullPointerException if the given {@code tree} is {@code null}
413      */
414     public static void prune(final TreeNode<Op<Double>> tree) {
415         MathExprSimplifier.prune(tree);
416     }
417 
418 }