6705ed211c28f5e0412f8cee807be7d28e9b6500
[moodle.git] / lib / evalmath / evalmath.class.php
1 <?php
3 /*
4 ================================================================================
6 EvalMath - PHP Class to safely evaluate math expressions
7 Copyright (C) 2005 Miles Kaufmann <http://www.twmagic.com/>
9 ================================================================================
11 NAME
12     EvalMath - safely evaluate math expressions
14 SYNOPSIS
15     <?
16       include('evalmath.class.php');
17       $m = new EvalMath;
18       // basic evaluation:
19       $result = $m->evaluate('2+2');
20       // supports: order of operation; parentheses; negation; built-in functions
21       $result = $m->evaluate('-8(5/2)^2*(1-sqrt(4))-8');
22       // create your own variables
23       $m->evaluate('a = e^(ln(pi))');
24       // or functions
25       $m->evaluate('f(x,y) = x^2 + y^2 - 2x*y + 1');
26       // and then use them
27       $result = $m->evaluate('3*f(42,a)');
28     ?>
30 DESCRIPTION
31     Use the EvalMath class when you want to evaluate mathematical expressions
32     from untrusted sources.  You can define your own variables and functions,
33     which are stored in the object.  Try it, it's fun!
35 METHODS
36     $m->evalute($expr)
37         Evaluates the expression and returns the result.  If an error occurs,
38         prints a warning and returns false.  If $expr is a function assignment,
39         returns true on success.
41     $m->e($expr)
42         A synonym for $m->evaluate().
44     $m->vars()
45         Returns an associative array of all user-defined variables and values.
47     $m->funcs()
48         Returns an array of all user-defined functions.
50 PARAMETERS
51     $m->suppress_errors
52         Set to true to turn off warnings when evaluating expressions
54     $m->last_error
55         If the last evaluation failed, contains a string describing the error.
56         (Useful when suppress_errors is on).
58 AUTHOR INFORMATION
59     Copyright 2005, Miles Kaufmann.
61 LICENSE
62     Redistribution and use in source and binary forms, with or without
63     modification, are permitted provided that the following conditions are
64     met:
66     1   Redistributions of source code must retain the above copyright
67         notice, this list of conditions and the following disclaimer.
68     2.  Redistributions in binary form must reproduce the above copyright
69         notice, this list of conditions and the following disclaimer in the
70         documentation and/or other materials provided with the distribution.
71     3.  The name of the author may not be used to endorse or promote
72         products derived from this software without specific prior written
73         permission.
75     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
76     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
77     WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
78     DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
79     INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
80     (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
81     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
82     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
83     STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
84     ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
85     POSSIBILITY OF SUCH DAMAGE.
87 */
89 /**
90  * This class was heavily modified in order to get usefull spreadsheet emulation ;-)
91  * skodak
92  *
93  */
95 class EvalMath {
97     /** @var string Pattern used for a valid function or variable name. Note, var and func names are case insensitive.*/
98     private static $namepat = '[a-z][a-z0-9_]*';
100     var $suppress_errors = false;
101     var $last_error = null;
103     var $v = array(); // variables (and constants)
104     var $f = array(); // user-defined functions
105     var $vb = array(); // constants
106     var $fb = array(  // built-in functions
107         'sin','sinh','arcsin','asin','arcsinh','asinh',
108         'cos','cosh','arccos','acos','arccosh','acosh',
109         'tan','tanh','arctan','atan','arctanh','atanh',
110         'sqrt','abs','ln','log','exp','floor','ceil','round');
112     var $fc = array( // calc functions emulation
113         'average'=>array(-1), 'max'=>array(-1),  'min'=>array(-1),
114         'mod'=>array(2),      'pi'=>array(0),    'power'=>array(2),
115         'round'=>array(1, 2), 'sum'=>array(-1), 'rand_int'=>array(2),
116         'rand_float'=>array(0));
118     var $allowimplicitmultiplication;
120     function EvalMath($allowconstants = false, $allowimplicitmultiplication = false) {
121         if ($allowconstants){
122             $this->v['pi'] = pi();
123             $this->v['e'] = exp(1);
124         }
125         $this->allowimplicitmultiplication = $allowimplicitmultiplication;
126     }
128     function e($expr) {
129         return $this->evaluate($expr);
130     }
132     function evaluate($expr) {
133         $this->last_error = null;
134         $expr = trim($expr);
135         if (substr($expr, -1, 1) == ';') $expr = substr($expr, 0, strlen($expr)-1); // strip semicolons at the end
136         //===============
137         // is it a variable assignment?
138         if (preg_match('/^\s*('.self::$namepat.')\s*=\s*(.+)$/', $expr, $matches)) {
139             if (in_array($matches[1], $this->vb)) { // make sure we're not assigning to a constant
140                 return $this->trigger(get_string('cannotassigntoconstant', 'mathslib', $matches[1]));
141             }
142             if (($tmp = $this->pfx($this->nfx($matches[2]))) === false) return false; // get the result and make sure it's good
143             $this->v[$matches[1]] = $tmp; // if so, stick it in the variable array
144             return $this->v[$matches[1]]; // and return the resulting value
145         //===============
146         // is it a function assignment?
147         } elseif (preg_match('/^\s*('.self::$namepat.')\s*\(\s*('.self::$namepat.'(?:\s*,\s*'.self::$namepat.')*)\s*\)\s*=\s*(.+)$/', $expr, $matches)) {
148             $fnn = $matches[1]; // get the function name
149             if (in_array($matches[1], $this->fb)) { // make sure it isn't built in
150                 return $this->trigger(get_string('cannotredefinebuiltinfunction', 'mathslib', $matches[1]));
151             }
152             $args = explode(",", preg_replace("/\s+/", "", $matches[2])); // get the arguments
153             if (($stack = $this->nfx($matches[3])) === false) return false; // see if it can be converted to postfix
154             for ($i = 0; $i<count($stack); $i++) { // freeze the state of the non-argument variables
155                 $token = $stack[$i];
156                 if (preg_match('/^'.self::$namepat.'$/', $token) and !in_array($token, $args)) {
157                     if (array_key_exists($token, $this->v)) {
158                         $stack[$i] = $this->v[$token];
159                     } else {
160                         return $this->trigger(get_string('undefinedvariableinfunctiondefinition', 'mathslib', $token));
161                     }
162                 }
163             }
164             $this->f[$fnn] = array('args'=>$args, 'func'=>$stack);
165             return true;
166         //===============
167         } else {
168             return $this->pfx($this->nfx($expr)); // straight up evaluation, woo
169         }
170     }
172     function vars() {
173         return $this->v;
174     }
176     function funcs() {
177         $output = array();
178         foreach ($this->f as $fnn=>$dat)
179             $output[] = $fnn . '(' . implode(',', $dat['args']) . ')';
180         return $output;
181     }
183     /**
184      * @param string $name
185      * @return boolean Is this a valid var or function name?
186      */
187     public static function is_valid_var_or_func_name($name){
188         return preg_match('/'.self::$namepat.'$/iA', $name);
189     }
191     //===================== HERE BE INTERNAL METHODS ====================\\
193     // Convert infix to postfix notation
194     function nfx($expr) {
196         $index = 0;
197         $stack = new EvalMathStack;
198         $output = array(); // postfix form of expression, to be passed to pfx()
199         $expr = trim(strtolower($expr));
201         $ops   = array('+', '-', '*', '/', '^', '_');
202         $ops_r = array('+'=>0,'-'=>0,'*'=>0,'/'=>0,'^'=>1); // right-associative operator?
203         $ops_p = array('+'=>0,'-'=>0,'*'=>1,'/'=>1,'_'=>1,'^'=>2); // operator precedence
205         $expecting_op = false; // we use this in syntax-checking the expression
206                                // and determining when a - is a negation
208         if (preg_match("/[^\w\s+*^\/()\.,-]/", $expr, $matches)) { // make sure the characters are all good
209             return $this->trigger(get_string('illegalcharactergeneral', 'mathslib', $matches[0]));
210         }
212         while(1) { // 1 Infinite Loop ;)
213             $op = substr($expr, $index, 1); // get the first character at the current index
214             // find out if we're currently at the beginning of a number/variable/function/parenthesis/operand
215             $ex = preg_match('/^('.self::$namepat.'\(?|\d+(?:\.\d*)?(?:(e[+-]?)\d*)?|\.\d+|\()/', substr($expr, $index), $match);
216             //===============
217             if ($op == '-' and !$expecting_op) { // is it a negation instead of a minus?
218                 $stack->push('_'); // put a negation on the stack
219                 $index++;
220             } elseif ($op == '_') { // we have to explicitly deny this, because it's legal on the stack
221                 return $this->trigger(get_string('illegalcharacterunderscore', 'mathslib')); // but not in the input expression
222             //===============
223             } elseif ((in_array($op, $ops) or $ex) and $expecting_op) { // are we putting an operator on the stack?
224                 if ($ex) { // are we expecting an operator but have a number/variable/function/opening parethesis?
225                     if (!$this->allowimplicitmultiplication){
226                         return $this->trigger(get_string('implicitmultiplicationnotallowed', 'mathslib'));
227                     } else {// it's an implicit multiplication
228                         $op = '*';
229                         $index--;
230                     }
231                 }
232                 // heart of the algorithm:
233                 while($stack->count > 0 and ($o2 = $stack->last()) and in_array($o2, $ops) and ($ops_r[$op] ? $ops_p[$op] < $ops_p[$o2] : $ops_p[$op] <= $ops_p[$o2])) {
234                     $output[] = $stack->pop(); // pop stuff off the stack into the output
235                 }
236                 // many thanks: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_algorithm_in_detail
237                 $stack->push($op); // finally put OUR operator onto the stack
238                 $index++;
239                 $expecting_op = false;
240             //===============
241             } elseif ($op == ')' and $expecting_op) { // ready to close a parenthesis?
242                 while (($o2 = $stack->pop()) != '(') { // pop off the stack back to the last (
243                     if (is_null($o2)) return $this->trigger(get_string('unexpectedclosingbracket', 'mathslib'));
244                     else $output[] = $o2;
245                 }
246                 if (preg_match('/^('.self::$namepat.')\($/', $stack->last(2), $matches)) { // did we just close a function?
247                     $fnn = $matches[1]; // get the function name
248                     $arg_count = $stack->pop(); // see how many arguments there were (cleverly stored on the stack, thank you)
249                     $fn = $stack->pop();
250                     $output[] = array('fn'=>$fn, 'fnn'=>$fnn, 'argcount'=>$arg_count); // send function to output
251                     if (in_array($fnn, $this->fb)) { // check the argument count
252                         if($arg_count > 1) {
253                             $a= new stdClass();
254                             $a->expected = 1;
255                             $a->given = $arg_count;
256                             return $this->trigger(get_string('wrongnumberofarguments', 'mathslib', $a));
257                         }
258                     } elseif (array_key_exists($fnn, $this->fc)) {
259                         $counts = $this->fc[$fnn];
260                         if (in_array(-1, $counts) and $arg_count > 0) {}
261                         elseif (!in_array($arg_count, $counts)) {
262                             $a= new stdClass();
263                             $a->expected = implode('/',$this->fc[$fnn]);
264                             $a->given = $arg_count;
265                             return $this->trigger(get_string('wrongnumberofarguments', 'mathslib', $a));
266                         }
267                     } elseif (array_key_exists($fnn, $this->f)) {
268                         if ($arg_count != count($this->f[$fnn]['args'])) {
269                             $a= new stdClass();
270                             $a->expected = count($this->f[$fnn]['args']);
271                             $a->given = $arg_count;
272                             return $this->trigger(get_string('wrongnumberofarguments', 'mathslib', $a));
273                         }
274                     } else { // did we somehow push a non-function on the stack? this should never happen
275                         return $this->trigger(get_string('internalerror', 'mathslib'));
276                     }
277                 }
278                 $index++;
279             //===============
280             } elseif ($op == ',' and $expecting_op) { // did we just finish a function argument?
281                 while (($o2 = $stack->pop()) != '(') {
282                     if (is_null($o2)) return $this->trigger(get_string('unexpectedcomma', 'mathslib')); // oops, never had a (
283                     else $output[] = $o2; // pop the argument expression stuff and push onto the output
284                 }
285                 // make sure there was a function
286                 if (!preg_match('/^('.self::$namepat.')\($/', $stack->last(2), $matches))
287                     return $this->trigger(get_string('unexpectedcomma', 'mathslib'));
288                 $stack->push($stack->pop()+1); // increment the argument count
289                 $stack->push('('); // put the ( back on, we'll need to pop back to it again
290                 $index++;
291                 $expecting_op = false;
292             //===============
293             } elseif ($op == '(' and !$expecting_op) {
294                 $stack->push('('); // that was easy
295                 $index++;
296                 $allow_neg = true;
297             //===============
298             } elseif ($ex and !$expecting_op) { // do we now have a function/variable/number?
299                 $expecting_op = true;
300                 $val = $match[1];
301                 if (preg_match('/^('.self::$namepat.')\($/', $val, $matches)) { // may be func, or variable w/ implicit multiplication against parentheses...
302                     if (in_array($matches[1], $this->fb) or array_key_exists($matches[1], $this->f) or array_key_exists($matches[1], $this->fc)) { // it's a func
303                         $stack->push($val);
304                         $stack->push(1);
305                         $stack->push('(');
306                         $expecting_op = false;
307                     } else { // it's a var w/ implicit multiplication
308                         $val = $matches[1];
309                         $output[] = $val;
310                     }
311                 } else { // it's a plain old var or num
312                     $output[] = $val;
313                 }
314                 $index += strlen($val);
315             //===============
316             } elseif ($op == ')') {
317                 //it could be only custom function with no params or general error
318                 if ($stack->last() != '(' or $stack->last(2) != 1) return $this->trigger(get_string('unexpectedclosingbracket', 'mathslib'));
319                 if (preg_match('/^('.self::$namepat.')\($/', $stack->last(3), $matches)) { // did we just close a function?
320                     $stack->pop();// (
321                     $stack->pop();// 1
322                     $fn = $stack->pop();
323                     $fnn = $matches[1]; // get the function name
324                     $counts = $this->fc[$fnn];
325                     if (!in_array(0, $counts)){
326                         $a= new stdClass();
327                         $a->expected = $this->fc[$fnn];
328                         $a->given = 0;
329                         return $this->trigger(get_string('wrongnumberofarguments', 'mathslib', $a));
330                     }
331                     $output[] = array('fn'=>$fn, 'fnn'=>$fnn, 'argcount'=>0); // send function to output
332                     $index++;
333                     $expecting_op = true;
334                 } else {
335                     return $this->trigger(get_string('unexpectedclosingbracket', 'mathslib'));
336                 }
337             //===============
338             } elseif (in_array($op, $ops) and !$expecting_op) { // miscellaneous error checking
339                 return $this->trigger(get_string('unexpectedoperator', 'mathslib', $op));
340             } else { // I don't even want to know what you did to get here
341                 return $this->trigger(get_string('anunexpectederroroccured', 'mathslib'));
342             }
343             if ($index == strlen($expr)) {
344                 if (in_array($op, $ops)) { // did we end with an operator? bad.
345                     return $this->trigger(get_string('operatorlacksoperand', 'mathslib', $op));
346                 } else {
347                     break;
348                 }
349             }
350             while (substr($expr, $index, 1) == ' ') { // step the index past whitespace (pretty much turns whitespace
351                 $index++;                             // into implicit multiplication if no operator is there)
352             }
354         }
355         while (!is_null($op = $stack->pop())) { // pop everything off the stack and push onto output
356             if ($op == '(') return $this->trigger(get_string('expectingaclosingbracket', 'mathslib')); // if there are (s on the stack, ()s were unbalanced
357             $output[] = $op;
358         }
359         return $output;
360     }
362     // evaluate postfix notation
363     function pfx($tokens, $vars = array()) {
365         if ($tokens == false) return false;
367         $stack = new EvalMathStack;
369         foreach ($tokens as $token) { // nice and easy
371             // if the token is a function, pop arguments off the stack, hand them to the function, and push the result back on
372             if (is_array($token)) { // it's a function!
373                 $fnn = $token['fnn'];
374                 $count = $token['argcount'];
375                 if (in_array($fnn, $this->fb)) { // built-in function:
376                     if (is_null($op1 = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
377                     $fnn = preg_replace("/^arc/", "a", $fnn); // for the 'arc' trig synonyms
378                     if ($fnn == 'ln') $fnn = 'log';
379                     eval('$stack->push(' . $fnn . '($op1));'); // perfectly safe eval()
380                 } elseif (array_key_exists($fnn, $this->fc)) { // calc emulation function
381                     // get args
382                     $args = array();
383                     for ($i = $count-1; $i >= 0; $i--) {
384                         if (is_null($args[] = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
385                     }
386                     $classname = 'EvalMathCalcEmul_'.$fnn;
387                     $res = call_user_func(array($classname, 'calculate'), $args);
388                     if ($res === FALSE) {
389                         return $this->trigger(get_string('internalerror', 'mathslib'));
390                     }
391                     $stack->push($res);
392                 } elseif (array_key_exists($fnn, $this->f)) { // user function
393                     // get args
394                     $args = array();
395                     for ($i = count($this->f[$fnn]['args'])-1; $i >= 0; $i--) {
396                         if (is_null($args[$this->f[$fnn]['args'][$i]] = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
397                     }
398                     $stack->push($this->pfx($this->f[$fnn]['func'], $args)); // yay... recursion!!!!
399                 }
400             // if the token is a binary operator, pop two values off the stack, do the operation, and push the result back on
401             } elseif (in_array($token, array('+', '-', '*', '/', '^'), true)) {
402                 if (is_null($op2 = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
403                 if (is_null($op1 = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
404                 switch ($token) {
405                     case '+':
406                         $stack->push($op1+$op2); break;
407                     case '-':
408                         $stack->push($op1-$op2); break;
409                     case '*':
410                         $stack->push($op1*$op2); break;
411                     case '/':
412                         if ($op2 == 0) return $this->trigger(get_string('divisionbyzero', 'mathslib'));
413                         $stack->push($op1/$op2); break;
414                     case '^':
415                         $stack->push(pow($op1, $op2)); break;
416                 }
417             // if the token is a unary operator, pop one value off the stack, do the operation, and push it back on
418             } elseif ($token == "_") {
419                 $stack->push(-1*$stack->pop());
420             // if the token is a number or variable, push it on the stack
421             } else {
422                 if (is_numeric($token)) {
423                     $stack->push($token);
424                 } elseif (array_key_exists($token, $this->v)) {
425                     $stack->push($this->v[$token]);
426                 } elseif (array_key_exists($token, $vars)) {
427                     $stack->push($vars[$token]);
428                 } else {
429                     return $this->trigger(get_string('undefinedvariable', 'mathslib', $token));
430                 }
431             }
432         }
433         // when we're out of tokens, the stack should have a single element, the final result
434         if ($stack->count != 1) return $this->trigger(get_string('internalerror', 'mathslib'));
435         return $stack->pop();
436     }
438     // trigger an error, but nicely, if need be
439     function trigger($msg) {
440         $this->last_error = $msg;
441         if (!$this->suppress_errors) trigger_error($msg, E_USER_WARNING);
442         return false;
443     }
447 // for internal use
448 class EvalMathStack {
450     var $stack = array();
451     var $count = 0;
453     function push($val) {
454         $this->stack[$this->count] = $val;
455         $this->count++;
456     }
458     function pop() {
459         if ($this->count > 0) {
460             $this->count--;
461             return $this->stack[$this->count];
462         }
463         return null;
464     }
466     function last($n=1) {
467         if ($this->count - $n >= 0) {
468             return $this->stack[$this->count-$n];
469         }
470         return null;
471     }
475 // spreadsheet functions emulation
476 // watch out for reversed args!!
477 class EvalMathCalcEmul_average {
479     static function calculate($args) {
480         return (EvalMathCalcEmul_sum::calculate($args)/count($args));
481     }
484 class EvalMathCalcEmul_max  {
485     static function calculate($args) {
486         $res = array_pop($args);
487         foreach($args as $a) {
488             if ($res < $a) {
489                 $res = $a;
490             }
491         }
492         return $res;
493     }
496 class EvalMathCalcEmul_min  {
497     static function calculate($args) {
498         $res = array_pop($args);
499         foreach($args as $a) {
500             if ($res > $a) {
501                 $res = $a;
502             }
503         }
504         return $res;
505     }
507 class EvalMathCalcEmul_mod {
508     static function calculate($args) {
509         return $args[1] % $args[0];
510     }
512 class EvalMathCalcEmul_pi {
513     static function calculate($args) {
514         return pi();
515     }
517 class EvalMathCalcEmul_power {
518     static function calculate($args) {
519         return $args[1]^$args[0];
520     }
523 class EvalMathCalcEmul_round {
524     static function calculate($args) {
525         if (count($args)==1) {
526             return round($args[0]);
527         } else {
528             return round($args[1], $args[0]);
529         }
530     }
532 class EvalMathCalcEmul_sum {
533     static function calculate($args) {
534         $res = 0;
535         foreach($args as $a) {
536            $res += $a;
537         }
538         return $res;
539     }
541 class EvalMathCalcEmul_randomised {
542     protected static $randomseed = null;
544     static function set_random_seed($randomseed) {
545         self::$randomseed = $randomseed;
546     }
548     static function get_random_seed() {
549         if (is_null(self::$randomseed)){
550             return microtime();
551         } else {
552             return self::$randomseed;
553         }
554     }
558 class EvalMathCalcEmul_rand_int extends EvalMathCalcEmul_randomised {
559     static function calculate($args){
560         $min = $args[1];
561         $max = $args[0];
562         if ($min >= $max) {
563             return false; //error
564         }
565         $noofchars = ceil(log($max + 1 - $min, '16'));
566         $md5string = md5(self::get_random_seed());
567         $stringoffset = 0;
568         do {
569             while (($stringoffset + $noofchars) > strlen($md5string)){
570                 $md5string .= md5($md5string);
571             }
572             $randomno = hexdec(substr($md5string, $stringoffset, $noofchars));
573             $stringoffset += $noofchars;
574         } while (($min + $randomno) > $max);
575         return $min + $randomno;
576     }
578 class EvalMathCalcEmul_rand_float extends EvalMathCalcEmul_randomised {
579     static function calculate(){
580         $randomvalue = array_shift(unpack('v', md5(self::get_random_seed(), true)));
581         return $randomvalue / 65536;
582     }