Source code: jmat/function/expressionParser/Evaluator.java
1 package jmat.function.expressionParser;
2
3 import jmat.data.Matrix;
4 import jmat.data.RandomMatrix;
5
6 import java.lang.Double;
7
8 import java.util.HashMap;
9
10
11 /************************************************************************
12 * <i>Mathematic expression evaluator.</i> Supports the following functions:
13 * +, -, *, /, ^, %, cos, sin, tan, acos, asin, atan, sqrt, sqr, log, min, max, ceil, floor, abs, neg, rndr.<br>
14 * When the getValue() is called, a Double object is returned. If it returns null, an error occured.<p>
15 * <pre>
16 * Sample:
17 * MathEvaluator m = new MathEvaluator("-5-6/(-2) + sqr(15+x)");
18 * m.addVariable("x", 15.1d);
19 * System.out.println( m.getValue() );
20 * </pre>
21 * @version 1.1
22 * @author The-Son LAI, <a href="mailto:Lts@writeme.com">Lts@writeme.com</a>
23 * @date April 2001
24 ************************************************************************/
25 public class Evaluator
26 {
27 //~ Static fields/initializers /////////////////////////////////////////////
28
29 protected static Operator[] operators = null;
30
31 //~ Instance fields ////////////////////////////////////////////////////////
32
33 private HashMap variables = new HashMap();
34 private Node node = null;
35 private String expression = null;
36
37 //~ Constructors ///////////////////////////////////////////////////////////
38
39 /***
40 * creates an empty MathEvaluator. You need to use setExpression(String s) to assign a math expression string to it.
41 */
42 public Evaluator()
43 {
44 init();
45 }
46
47 /***
48 * creates a MathEvaluator and assign the math expression string.
49 */
50 public Evaluator(String s)
51 {
52 init();
53 setExpression(s);
54 }
55
56 //~ Methods ////////////////////////////////////////////////////////////////
57
58 /***
59 * sets the expression
60 */
61 public void setExpression(String s)
62 {
63 expression = s;
64 }
65
66 /***
67 * evaluates and returns the value of the expression
68 */
69 public Object getValue()
70 {
71 if (expression == null)
72 {
73 return null;
74 }
75
76 try
77 {
78 node = new Node(expression);
79
80 return (evaluate(node));
81 }
82 catch (Exception e)
83 {
84 e.printStackTrace();
85
86 return null;
87 }
88 }
89
90 /***
91 * gets the variable's value that was assigned previously
92 */
93 public Object getVariable(String s)
94 {
95 return variables.get(s);
96 }
97
98 /***
99 * adds a variable and its value in the MathEvaluator
100 */
101 public void addVariable(String v, Matrix val)
102 {
103 variables.put(v, val);
104 }
105
106 /***
107 * adds a variable and its value in the MathEvaluator
108 */
109 public void addVariable(String v, double val)
110 {
111 variables.put(v, new Double(val));
112 }
113
114 /***
115 * adds a variable and its value in the MathEvaluator
116 */
117 public void addVariable(String v, Double val)
118 {
119 variables.put(v, val);
120 }
121
122 /***
123 * resets the evaluator
124 */
125 public void reset()
126 {
127 node = null;
128 expression = null;
129 variables = new HashMap();
130 }
131
132 /***
133 * trace the binary tree for debug
134 */
135 public void trace()
136 {
137 try
138 {
139 node = new Node(expression);
140 node.trace();
141 }
142 catch (Exception e)
143 {
144 e.printStackTrace();
145 }
146 }
147
148 protected Operator[] getOperators()
149 {
150 return operators;
151 }
152
153 protected static void _D(String s)
154 {
155 System.err.println(s);
156 }
157
158 private static Object evaluate(Node n)
159 {
160 if (n.hasOperator() && n.hasChild())
161 {
162 if (n.getOperator().getType() == 1)
163 {
164 n.setValue(evaluateExpression1(n.getOperator(),
165 evaluate(n.getLeft())));
166 }
167 else if (n.getOperator().getType() == 2)
168 {
169 n.setValue(evaluateExpression2(n.getOperator(),
170 evaluate(n.getLeft()), evaluate(n.getRight())));
171 }
172 }
173
174 return (n.getValue());
175 }
176
177 private static Object evaluateExpression1(Operator o, Object o1)
178 {
179 String op = o.getOperator();
180 Object res = null;
181
182 boolean o1isMatrix;
183
184 try
185 {
186 Matrix m1 = (Matrix) o1;
187 m1 = null;
188 o1isMatrix = true;
189 }
190 catch (Exception e)
191 {
192 o1isMatrix = false;
193 }
194
195 if (o1isMatrix)
196 {
197 Matrix f1 = (Matrix) o1;
198
199 if ("t".equals(op))
200 {
201 res = (Object) (f1.transpose());
202 }
203 else if ("inv".equals(op))
204 {
205 res = (Object) (f1.inverse());
206 }
207 else if ("diag".equals(op))
208 {
209 res = (Object) (f1.diag());
210 }
211 else if ("det".equals(op))
212 {
213 res = (Object) (new Double((double) (f1.det())));
214 }
215 else if ("trace".equals(op))
216 {
217 res = (Object) (new Double((double) (f1.trace())));
218 }
219 else if ("rank".equals(op))
220 {
221 res = (Object) (new Double((double) (f1.rank())));
222 }
223 else if ("sum".equals(op))
224 {
225 res = (Object) (f1.sum());
226 }
227 else if ("prod".equals(op))
228 {
229 res = (Object) (f1.prod());
230 }
231 else if ("min".equals(op))
232 {
233 res = (Object) (f1.min());
234 }
235 else if ("max".equals(op))
236 {
237 res = (Object) (f1.max());
238 }
239 else if ("mean".equals(op))
240 {
241 res = (Object) (((RandomMatrix) (f1)).mean());
242 }
243 else if ("cov".equals(op))
244 {
245 res = (Object) (((RandomMatrix) (f1)).cov());
246 }
247 else if ("var".equals(op))
248 {
249 res = (Object) (((RandomMatrix) (f1)).var());
250 }
251 else if ("cor".equals(op))
252 {
253 res = (Object) (((RandomMatrix) (f1)).cor());
254 }
255 }
256 else
257 {
258 double f1 = ((Double) o1).doubleValue();
259
260 if ("cos".equals(op))
261 {
262 res = (Object) (new Double(Math.cos(f1)));
263 }
264 else if ("sin".equals(op))
265 {
266 res = (Object) (new Double(Math.sin(f1)));
267 }
268 else if ("tan".equals(op))
269 {
270 res = (Object) (new Double(Math.tan(f1)));
271 }
272 else if ("acos".equals(op))
273 {
274 res = (Object) (new Double(Math.acos(f1)));
275 }
276 else if ("asin".equals(op))
277 {
278 res = (Object) (new Double(Math.asin(f1)));
279 }
280 else if ("atan".equals(op))
281 {
282 res = (Object) (new Double(Math.atan(f1)));
283 }
284 else if ("sqrt".equals(op))
285 {
286 res = (Object) (new Double(Math.sqrt(f1)));
287 }
288 else if ("log".equals(op))
289 {
290 res = (Object) (new Double(Math.log(f1)));
291 }
292 else if ("exp".equals(op))
293 {
294 res = (Object) (new Double(Math.exp(f1)));
295 }
296 else if ("floor".equals(op))
297 {
298 res = (Object) (new Double(Math.floor(f1)));
299 }
300 else if ("ceil".equals(op))
301 {
302 res = (Object) (new Double(Math.ceil(f1)));
303 }
304 else if ("abs".equals(op))
305 {
306 res = (Object) (new Double(Math.abs(f1)));
307 }
308 }
309
310 return res;
311 }
312
313 private static Object evaluateExpression2(Operator o, Object o1, Object o2)
314 {
315 String op = o.getOperator();
316 Object res = null;
317
318 boolean o1isMatrix;
319 boolean o2isMatrix;
320
321 try
322 {
323 Matrix m1 = (Matrix) o1;
324 m1 = null;
325 o1isMatrix = true;
326 }
327 catch (Exception e)
328 {
329 o1isMatrix = false;
330 }
331
332 try
333 {
334 Matrix m2 = (Matrix) o2;
335 m2 = null;
336 o2isMatrix = true;
337 }
338 catch (Exception e)
339 {
340 o2isMatrix = false;
341 }
342
343 if (o1isMatrix)
344 {
345 Matrix f1 = (Matrix) o1;
346
347 if (o2isMatrix)
348 {
349 Matrix f2 = (Matrix) o2;
350
351 if ("+".equals(op))
352 {
353 res = (Object) (f1.plus(f2));
354 }
355 else if ("-".equals(op))
356 {
357 res = (Object) (f1.minus(f2));
358 }
359 else if ("*".equals(op))
360 {
361 res = (Object) (f1.times(f2));
362 }
363 else if ("/".equals(op))
364 {
365 res = (Object) (f1.divide(f2));
366 }
367 }
368 else
369 {
370 double f2 = ((Double) o2).doubleValue();
371
372 if ("*".equals(op))
373 {
374 res = (Object) (f1.times(f2));
375 }
376 else if ("/".equals(op))
377 {
378 res = (Object) (f1.divide(f2));
379 }
380 else if ("sort".equals(op))
381 {
382 res = (Object) (f1.sort(Math.round((float) f2)));
383 }
384 else if ("find".equals(op))
385 {
386 res = (Object) (f1.find(f2));
387 }
388 }
389 }
390 else
391 {
392 double f1 = ((Double) o1).doubleValue();
393
394 if (o2isMatrix)
395 {
396 Matrix f2 = (Matrix) o2;
397
398 if ("*".equals(op))
399 {
400 res = (Object) (f2.times(f1));
401 }
402 }
403 else
404 {
405 double f2 = ((Double) o2).doubleValue();
406
407 if ("+".equals(op))
408 {
409 res = (Object) (new Double(f1 + f2));
410 }
411 else if ("-".equals(op))
412 {
413 res = (Object) (new Double(f1 - f2));
414 }
415 else if ("*".equals(op))
416 {
417 res = (Object) (new Double(f1 * f2));
418 }
419 else if ("/".equals(op))
420 {
421 res = (Object) (new Double(f1 / f2));
422 }
423 else if ("^".equals(op))
424 {
425 res = (Object) (new Double(Math.pow(f1, f2)));
426 }
427 else if ("%".equals(op))
428 {
429 res = (Object) (new Double(f1 % f2));
430 }
431 else if ("min".equals(op))
432 {
433 res = (Object) (new Double(Math.min(f1, f2)));
434 }
435 else if ("max".equals(op))
436 {
437 res = (Object) (new Double(Math.max(f1, f2)));
438 }
439 else if ("&".equals(op))
440 {
441 res = (Object) (new Double(((f1 > 0) && (f2 > 0)) ? (1) : (0)));
442 }
443 else if ("|".equals(op))
444 {
445 res = (Object) (new Double(((f1 > 0) || (f2 > 0)) ? (1) : (0)));
446 }
447 else if ("<".equals(op))
448 {
449 res = (Object) (new Double((f1 < f2) ? (1) : (0)));
450 }
451 else if (">".equals(op))
452 {
453 res = (Object) (new Double((f1 > f2) ? (1) : (0)));
454 }
455 else if ("=".equals(op))
456 {
457 res = (Object) (new Double((f1 == f2) ? (1) : (0)));
458 }
459 }
460 }
461
462 return res;
463 }
464
465 private Object getObject(String s)
466 {
467 if (s == null)
468 {
469 return null;
470 }
471
472 Object res = null;
473
474 try
475 {
476 res = new Double(Double.parseDouble(s));
477 }
478 catch (Exception e)
479 {
480 return getVariable(s);
481 }
482
483 return res;
484 }
485
486 private void init()
487 {
488 if (operators == null)
489 {
490 initializeOperators();
491 }
492 }
493
494 private void initializeOperators()
495 {
496 operators = new Operator[39];
497
498 operators[0] = new Operator("+", 2, 0);
499 operators[1] = new Operator("-", 2, 0);
500 operators[2] = new Operator("*", 2, 10);
501 operators[3] = new Operator("/", 2, 10);
502 operators[4] = new Operator("t", 1, 20);
503 operators[5] = new Operator("inv", 1, 20);
504 operators[6] = new Operator("diag", 1, 20);
505 operators[7] = new Operator("det", 1, 20);
506 operators[8] = new Operator("trace", 1, 20);
507 operators[9] = new Operator("rank", 1, 20);
508 operators[10] = new Operator("sum", 1, 20);
509 operators[11] = new Operator("prod", 1, 20);
510 operators[12] = new Operator("min", 1, 20);
511 operators[13] = new Operator("max", 1, 20);
512 operators[14] = new Operator("mean", 1, 20);
513 operators[15] = new Operator("cov", 1, 20);
514 operators[16] = new Operator("var", 1, 20);
515 operators[17] = new Operator("cor", 1, 20);
516 operators[18] = new Operator("sort", 2, 20);
517 operators[19] = new Operator("find", 2, 20);
518 operators[20] = new Operator("%", 2, 10);
519 operators[21] = new Operator("^", 2, 10);
520 operators[22] = new Operator("cos", 1, 20);
521 operators[23] = new Operator("sin", 1, 20);
522 operators[24] = new Operator("tan", 1, 20);
523 operators[25] = new Operator("acos", 1, 20);
524 operators[26] = new Operator("asin", 1, 20);
525 operators[27] = new Operator("atan", 1, 20);
526 operators[28] = new Operator("sqrt", 1, 20);
527 operators[29] = new Operator("exp", 1, 20);
528 operators[30] = new Operator("log", 1, 20);
529 operators[31] = new Operator("floor", 1, 20);
530 operators[32] = new Operator("ceil", 1, 20);
531 operators[33] = new Operator("abs", 1, 20);
532 operators[34] = new Operator("&", 2, 0);
533 operators[35] = new Operator("|", 2, 0);
534 operators[36] = new Operator("<", 2, 0);
535 operators[37] = new Operator(">", 2, 0);
536 operators[38] = new Operator("=", 2, 0);
537 }
538
539 //~ Inner Classes //////////////////////////////////////////////////////////
540
541 protected class Node
542 {
543 public Node nLeft = null;
544 public Node nParent = null;
545 public Node nRight = null;
546 public Object nValue = null;
547 public Operator nOperator = null;
548 public String nString = null;
549 public int nLevel = 0;
550
551 public Node(String s) throws Exception
552 {
553 init(null, s, 0);
554 }
555
556 public Node(Node parent, String s, int level) throws Exception
557 {
558 init(parent, s, level);
559 }
560
561 /***
562 * Removes spaces, tabs and brackets at the begining
563 */
564 public String removeBrackets(String s)
565 {
566 String res = s;
567
568 if ((s.length() > 2) && res.startsWith("(") && res.endsWith(")") &&
569 (checkBrackets(s.substring(1, s.length() - 1)) == 0))
570 {
571 res = res.substring(1, res.length() - 1);
572 }
573
574 if (res != s)
575 {
576 return removeBrackets(res);
577 }
578 else
579 {
580 return res;
581 }
582 }
583
584 /***
585 * Removes illegal characters
586 */
587 public String removeIllegalCharacters(String s)
588 {
589 char[] illegalCharacters = {' '};
590 String res = s;
591
592 for (int j = 0; j < illegalCharacters.length; j++)
593 {
594 int i = res.lastIndexOf(illegalCharacters[j], res.length());
595
596 while (i != -1)
597 {
598 String temp = res;
599 res = temp.substring(0, i);
600 res += temp.substring(i + 1);
601 i = res.lastIndexOf(illegalCharacters[j], s.length());
602 }
603 }
604
605 return res;
606 }
607
608 /***
609 * displays the tree of the expression
610 */
611 public void trace()
612 {
613 String op = (getOperator() == null) ? " "
614 : getOperator().getOperator();
615 _D(op + " : " + getString());
616
617 if (this.hasChild())
618 {
619 if (hasLeft())
620 {
621 getLeft().trace();
622 }
623
624 if (hasRight())
625 {
626 getRight().trace();
627 }
628 }
629 }
630
631 protected Node getLeft()
632 {
633 return nLeft;
634 }
635
636 protected int getLevel()
637 {
638 return nLevel;
639 }
640
641 protected Operator getOperator()
642 {
643 return nOperator;
644 }
645
646 protected Node getRight()
647 {
648 return nRight;
649 }
650
651 protected String getString()
652 {
653 return nString;
654 }
655
656 protected void setValue(Object f)
657 {
658 nValue = f;
659 }
660
661 protected Object getValue()
662 {
663 return nValue;
664 }
665
666 protected void _D(String s)
667 {
668 String nbSpaces = "";
669
670 for (int i = 0; i < nLevel; i++)
671 {
672 nbSpaces += " ";
673 }
674
675 System.out.println(nbSpaces + "|" + s);
676 }
677
678 /***
679 * returns a string that doesnt start with a + or a -
680 */
681 protected String addZero(String s)
682 {
683 if (s.startsWith("+") || s.startsWith("-"))
684 {
685 int sLength = s.length();
686
687 for (int i = 0; i < sLength; i++)
688 {
689 if (getOperator(s, i) != null)
690 {
691 return "0" + s;
692 }
693 }
694 }
695
696 return s;
697 }
698
699 /***
700 * checks if there is any missing brackets
701 * @return true if s is valid
702 */
703 protected int checkBrackets(String s)
704 {
705 int sLength = s.length();
706 int inBracket = 0;
707
708 for (int i = 0; i < sLength; i++)
709 {
710 if ((s.charAt(i) == '(') && (inBracket >= 0))
711 {
712 inBracket++;
713 }
714 else if (s.charAt(i) == ')')
715 {
716 inBracket--;
717 }
718 }
719
720 return inBracket;
721 }
722
723 protected boolean hasChild()
724 {
725 return ((nLeft != null) || (nRight != null));
726 }
727
728 protected boolean hasLeft()
729 {
730 return (nLeft != null);
731 }
732
733 protected boolean hasOperator()
734 {
735 return (nOperator != null);
736 }
737
738 protected boolean hasRight()
739 {
740 return (nRight != null);
741 }
742
743 private String getNextWord(String s)
744 {
745 int sLength = s.length();
746
747 for (int i = 1; i < sLength; i++)
748 {
749 char c = s.charAt(i);
750
751 if (((c > 'z') || (c < 'a')) && ((c > '9') || (c < '0')))
752 {
753 return s.substring(0, i);
754 }
755 }
756
757 return s;
758 }
759
760 private Operator getOperator(String s, int start)
761 {
762 Operator[] operators = getOperators();
763 String temp = s.substring(start);
764 temp = getNextWord(temp);
765
766 for (int i = 0; i < operators.length; i++)
767 {
768 if (temp.startsWith(operators[i].getOperator()))
769 {
770 return operators[i];
771 }
772 }
773
774 return null;
775 }
776
777 private void init(Node parent, String s, int level)
778 throws Exception
779 {
780 s = removeIllegalCharacters(s);
781 s = removeBrackets(s);
782 s = addZero(s);
783
784 if (checkBrackets(s) != 0)
785 {
786 throw new Exception("Wrong number of brackets in [" + s + "]");
787 }
788
789 nParent = parent;
790 nString = s;
791 nValue = getObject(s);
792 nLevel = level;
793
794 int sLength = s.length();
795 int inBrackets = 0;
796 int startOperator = 0;
797
798 for (int i = 0; i < sLength; i++)
799 {
800 if (s.charAt(i) == '(')
801 {
802 inBrackets++;
803 }
804 else if (s.charAt(i) == ')')
805 {
806 inBrackets--;
807 }
808 else
809 {
810 // the expression must be at "root" level
811 if (inBrackets == 0)
812 {
813 Operator o = getOperator(nString, i);
814
815 if (o != null)
816 {
817 // if first operator or lower priority operator
818 if ((nOperator == null) ||
819 (nOperator.getPriority() >= o.getPriority()))
820 {
821 nOperator = o;
822 startOperator = i;
823 }
824 }
825 }
826 }
827 }
828
829 if (nOperator != null)
830 {
831 // one operand, should always be at the beginning
832 if ((startOperator == 0) && (nOperator.getType() == 1))
833 {
834 // the brackets must be ok
835 if (checkBrackets(s.substring(nOperator.getOperator()
836 .length())) == 0)
837 {
838 nLeft = new Node(this,
839 s.substring(nOperator.getOperator().length()),
840 nLevel + 1);
841 nRight = null;
842
843 return;
844 }
845 else
846 {
847 throw new Exception(
848 "Error during parsing... missing brackets in [" +
849 s + "]");
850 }
851 }
852
853 // two operands
854 else if ((startOperator > 0) && (nOperator.getType() == 2))
855 {
856 nOperator = nOperator;
857 nLeft = new Node(this, s.substring(0, startOperator),
858 nLevel + 1);
859 nRight = new Node(this,
860 s.substring(startOperator +
861 nOperator.getOperator().length()), nLevel + 1);
862 }
863 }
864 }
865 }
866
867 protected class Operator
868 {
869 private String op;
870 private int priority;
871 private int type;
872
873 public Operator(String o, int t, int p)
874 {
875 op = o;
876 type = t;
877 priority = p;
878 }
879
880 public void setOperator(String o)
881 {
882 op = o;
883 }
884
885 public String getOperator()
886 {
887 return op;
888 }
889
890 public int getPriority()
891 {
892 return priority;
893 }
894
895 public int getType()
896 {
897 return type;
898 }
899 }
900 }
901 ///////////////////////////////////////////////////////////////////////////////
902 // END OF FILE.
903 ///////////////////////////////////////////////////////////////////////////////