lib/evalmath/evalmath.class.php

   1 <?php
   2
   3 /*
   4 ================================================================================
   5
   6 EvalMath - PHP Class to safely evaluate math expressions
   7 Copyright (C) 2005 Miles Kaufmann <http://www.twmagic.com/>
   8
   9 ================================================================================
  10
  11 NAME
  12     EvalMath - safely evaluate math expressions
  13
  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     ?>
  29
  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!
  34
  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.
  40
  41     $m->e($expr)
  42         A synonym for $m->evaluate().
  43
  44     $m->vars()
  45         Returns an associative array of all user-defined variables and values.
  46
  47     $m->funcs()
  48         Returns an array of all user-defined functions.
  49
  50 PARAMETERS
  51     $m->suppress_errors
  52         Set to true to turn off warnings when evaluating expressions
  53
  54     $m->last_error
  55         If the last evaluation failed, contains a string describing the error.
  56         (Useful when suppress_errors is on).
  57
  58 AUTHOR INFORMATION
  59     Copyright 2005, Miles Kaufmann.
  60
  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:
  65
  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.
  74
  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.
  86
  87 */
  88
  89 /**
  90  * This class was heavily modified in order to get usefull spreadsheet emulation ;-)
  91  * skodak
  92  *
  93  */
  94
  95 class EvalMath {
  96
  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_]*';
  99
 100     var $suppress_errors = false;
 101     var $last_error = null;
 102
 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');
 111
 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));
 117
 118     var $allowimplicitmultiplication;
 119
 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     }
 127
 128     function e($expr) {
 129         return $this->evaluate($expr);
 130     }
 131
 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     }
 171
 172     function vars() {
 173         return $this->v;
 174     }
 175
 176     function funcs() {
 177         $output = array();
 178         foreach ($this->f as $fnn=>$dat)
 179             $output[] = $fnn . '(' . implode(',', $dat['args']) . ')';
 180         return $output;
 181     }
 182
 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     }
 190
 191     //===================== HERE BE INTERNAL METHODS ====================\\
 192
 193     // Convert infix to postfix notation
 194     function nfx($expr) {
 195
 196         $index = 0;
 197         $stack = new EvalMathStack;
 198         $output = array(); // postfix form of expression, to be passed to pfx()
 199         $expr = trim(strtolower($expr));
 200
 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
 204
 205         $expecting_op = false; // we use this in syntax-checking the expression
 206                                // and determining when a - is a negation
 207
 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         }
 211
 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             }
 353
 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     }
 361
 362     // evaluate postfix notation
 363     function pfx($tokens, $vars = array()) {
 364
 365         if ($tokens == false) return false;
 366
 367         $stack = new EvalMathStack;
 368
 369         foreach ($tokens as $token) { // nice and easy
 370
 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                     $res = call_user_func_array(array('EvalMathFuncs', $fnn), array_reverse($args));
 387                     if ($res === FALSE) {
 388                         return $this->trigger(get_string('internalerror', 'mathslib'));
 389                     }
 390                     $stack->push($res);
 391                 } elseif (array_key_exists($fnn, $this->f)) { // user function
 392                     // get args
 393                     $args = array();
 394                     for ($i = count($this->f[$fnn]['args'])-1; $i >= 0; $i--) {
 395                         if (is_null($args[$this->f[$fnn]['args'][$i]] = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
 396                     }
 397                     $stack->push($this->pfx($this->f[$fnn]['func'], $args)); // yay... recursion!!!!
 398                 }
 399             // if the token is a binary operator, pop two values off the stack, do the operation, and push the result back on
 400             } elseif (in_array($token, array('+', '-', '*', '/', '^'), true)) {
 401                 if (is_null($op2 = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
 402                 if (is_null($op1 = $stack->pop())) return $this->trigger(get_string('internalerror', 'mathslib'));
 403                 switch ($token) {
 404                     case '+':
 405                         $stack->push($op1+$op2); break;
 406                     case '-':
 407                         $stack->push($op1-$op2); break;
 408                     case '*':
 409                         $stack->push($op1*$op2); break;
 410                     case '/':
 411                         if ($op2 == 0) return $this->trigger(get_string('divisionbyzero', 'mathslib'));
 412                         $stack->push($op1/$op2); break;
 413                     case '^':
 414                         $stack->push(pow($op1, $op2)); break;
 415                 }
 416             // if the token is a unary operator, pop one value off the stack, do the operation, and push it back on
 417             } elseif ($token == "_") {
 418                 $stack->push(-1*$stack->pop());
 419             // if the token is a number or variable, push it on the stack
 420             } else {
 421                 if (is_numeric($token)) {
 422                     $stack->push($token);
 423                 } elseif (array_key_exists($token, $this->v)) {
 424                     $stack->push($this->v[$token]);
 425                 } elseif (array_key_exists($token, $vars)) {
 426                     $stack->push($vars[$token]);
 427                 } else {
 428                     return $this->trigger(get_string('undefinedvariable', 'mathslib', $token));
 429                 }
 430             }
 431         }
 432         // when we're out of tokens, the stack should have a single element, the final result
 433         if ($stack->count != 1) return $this->trigger(get_string('internalerror', 'mathslib'));
 434         return $stack->pop();
 435     }
 436
 437     // trigger an error, but nicely, if need be
 438     function trigger($msg) {
 439         $this->last_error = $msg;
 440         if (!$this->suppress_errors) trigger_error($msg, E_USER_WARNING);
 441         return false;
 442     }
 443
 444 }
 445
 446 // for internal use
 447 class EvalMathStack {
 448
 449     var $stack = array();
 450     var $count = 0;
 451
 452     function push($val) {
 453         $this->stack[$this->count] = $val;
 454         $this->count++;
 455     }
 456
 457     function pop() {
 458         if ($this->count > 0) {
 459             $this->count--;
 460             return $this->stack[$this->count];
 461         }
 462         return null;
 463     }
 464
 465     function last($n=1) {
 466         if ($this->count - $n >= 0) {
 467             return $this->stack[$this->count-$n];
 468         }
 469         return null;
 470     }
 471 }
 472
 473
 474 // spreadsheet functions emulation
 475 class EvalMathFuncs {
 476
 477     static function average() {
 478         $args = func_get_args();
 479         return (call_user_func_array(array('self', 'sum'), $args) / count($args));
 480     }
 481
 482     static function max() {
 483         $args = func_get_args();
 484         $res = array_pop($args);
 485         foreach($args as $a) {
 486             if ($res < $a) {
 487                 $res = $a;
 488             }
 489         }
 490         return $res;
 491     }
 492
 493     static function min() {
 494         $args = func_get_args();
 495         $res = array_pop($args);
 496         foreach($args as $a) {
 497             if ($res > $a) {
 498                 $res = $a;
 499             }
 500         }
 501         return $res;
 502     }
 503
 504     static function mod($op1, $op2) {
 505         return $op1 % $op2;
 506     }
 507
 508     static function pi() {
 509         return pi();
 510     }
 511
 512     static function power($op1, $op2) {
 513         return pow($op1, $op2);
 514     }
 515
 516     static function round($val, $precision = 0) {
 517         return round($val, $precision);
 518     }
 519
 520     static function sum() {
 521         $args = func_get_args();
 522         $res = 0;
 523         foreach($args as $a) {
 524            $res += $a;
 525         }
 526         return $res;
 527     }
 528
 529     protected static $randomseed = null;
 530
 531     static function set_random_seed($randomseed) {
 532         self::$randomseed = $randomseed;
 533     }
 534
 535     static function get_random_seed() {
 536         if (is_null(self::$randomseed)){
 537             return microtime();
 538         } else {
 539             return self::$randomseed;
 540         }
 541     }
 542
 543     static function rand_int($min, $max){
 544         if ($min >= $max) {
 545             return false; //error
 546         }
 547         $noofchars = ceil(log($max + 1 - $min, '16'));
 548         $md5string = md5(self::get_random_seed());
 549         $stringoffset = 0;
 550         do {
 551             while (($stringoffset + $noofchars) > strlen($md5string)){
 552                 $md5string .= md5($md5string);
 553             }
 554             $randomno = hexdec(substr($md5string, $stringoffset, $noofchars));
 555             $stringoffset += $noofchars;
 556         } while (($min + $randomno) > $max);
 557         return $min + $randomno;
 558     }
 559
 560     static function rand_float() {
 561         $randomvalues = unpack('v', md5(self::get_random_seed(), true));
 562         return array_shift($randomvalues) / 65536;
 563     }
 564 }