001 /*
002 * Java Genetic Algorithm Library (jenetics-4.1.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(((MathExpr) obj)._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 (brackets) out.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 (brackets) out.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 (brackets) out.append("(");
221 toString(tree.getChild(0), out);
222 out.append(op);
223 toString(tree.getChild(1), out);
224 if (brackets) out.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 out) throws 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 in) throws 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 }
|