lib/evalmath/evalmath.class.php

   1 <?
   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 $suppress_errors = false;
  98     var $last_error = null;
  99
 100     var $v = array(); // variables (and constants)
 101     var $f = array(); // user-defined functions
 102     var $vb = array(); // constants
 103     var $fb = array(  // built-in functions
 104         'sin','sinh','arcsin','asin','arcsinh','asinh',
 105         'cos','cosh','arccos','acos','arccosh','acosh',
 106         'tan','tanh','arctan','atan','arctanh','atanh',
 107         'sqrt','abs','ln','log','exp');
 108
 109     var $fc = array( // calc functions emulation
 110         'average'=>array(-1), 'max'=>array(-1),  'min'=>array(-1),
 111         'mod'=>array(2),      'pi'=>array(0),    'power'=>array(2),
 112         'round'=>array(1, 2), 'sum'=>array(-1));
 113
 114     function EvalMath() {
 115     }
 116
 117     function e($expr) {
 118         return $this->evaluate($expr);
 119     }
 120
 121     function evaluate($expr) {
 122         $this->last_error = null;
 123         $expr = trim($expr);
 124         if (substr($expr, -1, 1) == ';') $expr = substr($expr, 0, strlen($expr)-1); // strip semicolons at the end
 125         //===============
 126         // is it a variable assignment?
 127         if (preg_match('/^\s*([a-z][a-z0-9]*)\s*=\s*(.+)$/', $expr, $matches)) {
 128             if (in_array($matches[1], $this->vb)) { // make sure we're not assigning to a constant
 129                 return $this->trigger("cannot assign to constant '$matches[1]'");
 130             }
 131             if (($tmp = $this->pfx($this->nfx($matches[2]))) === false) return false; // get the result and make sure it's good
 132             $this->v[$matches[1]] = $tmp; // if so, stick it in the variable array
 133             return $this->v[$matches[1]]; // and return the resulting value
 134         //===============
 135         // is it a function assignment?
 136         } elseif (preg_match('/^\s*([a-z][a-z0-9]*)\s*\(\s*([a-z][a-z0-9]*(?:\s*,\s*[a-z][a-z0-9]*)*)\s*\)\s*=\s*(.+)$/', $expr, $matches)) {
 137             $fnn = $matches[1]; // get the function name
 138             if (in_array($matches[1], $this->fb)) { // make sure it isn't built in
 139                 return $this->trigger("cannot redefine built-in function '$matches[1]()'");
 140             }
 141             $args = explode(",", preg_replace("/\s+/", "", $matches[2])); // get the arguments
 142             if (($stack = $this->nfx($matches[3])) === false) return false; // see if it can be converted to postfix
 143             for ($i = 0; $i<count($stack); $i++) { // freeze the state of the non-argument variables
 144                 $token = $stack[$i];
 145                 if (preg_match('/^[a-z][a-z0-9]*$/', $token) and !in_array($token, $args)) {
 146                     if (array_key_exists($token, $this->v)) {
 147                         $stack[$i] = $this->v[$token];
 148                     } else {
 149                         return $this->trigger("undefined variable '$token' in function definition");
 150                     }
 151                 }
 152             }
 153             $this->f[$fnn] = array('args'=>$args, 'func'=>$stack);
 154             return true;
 155         //===============
 156         } else {
 157             return $this->pfx($this->nfx($expr)); // straight up evaluation, woo
 158         }
 159     }
 160
 161     function vars() {
 162         return $this->v;
 163     }
 164
 165     function funcs() {
 166         $output = array();
 167         foreach ($this->f as $fnn=>$dat)
 168             $output[] = $fnn . '(' . implode(',', $dat['args']) . ')';
 169         return $output;
 170     }
 171
 172     //===================== HERE BE INTERNAL METHODS ====================\\
 173
 174     // Convert infix to postfix notation
 175     function nfx($expr) {
 176
 177         $index = 0;
 178         $stack = new EvalMathStack;
 179         $output = array(); // postfix form of expression, to be passed to pfx()
 180         $expr = trim(strtolower($expr));
 181
 182         $ops   = array('+', '-', '*', '/', '^', '_');
 183         $ops_r = array('+'=>0,'-'=>0,'*'=>0,'/'=>0,'^'=>1); // right-associative operator?
 184         $ops_p = array('+'=>0,'-'=>0,'*'=>1,'/'=>1,'_'=>1,'^'=>2); // operator precedence
 185
 186         $expecting_op = false; // we use this in syntax-checking the expression
 187                                // and determining when a - is a negation
 188
 189         if (preg_match("/[^\w\s+*^\/()\.,-]/", $expr, $matches)) { // make sure the characters are all good
 190             return $this->trigger("illegal character '{$matches[0]}'");
 191         }
 192
 193         while(1) { // 1 Infinite Loop ;)
 194             $op = substr($expr, $index, 1); // get the first character at the current index
 195             // find out if we're currently at the beginning of a number/variable/function/parenthesis/operand
 196             $ex = preg_match('/^([a-z][a-z0-9]*\(?|\d+(?:\.\d*)?|\.\d+|\()/', substr($expr, $index), $match);
 197             //===============
 198             if ($op == '-' and !$expecting_op) { // is it a negation instead of a minus?
 199                 $stack->push('_'); // put a negation on the stack
 200                 $index++;
 201             } elseif ($op == '_') { // we have to explicitly deny this, because it's legal on the stack
 202                 return $this->trigger("illegal character '_'"); // but not in the input expression
 203             //===============
 204             } elseif ((in_array($op, $ops) or $ex) and $expecting_op) { // are we putting an operator on the stack?
 205                 if ($ex) { // are we expecting an operator but have a number/variable/function/opening parethesis?
 206                     return $this->trigger("expecting operand");
 207                     //$op = '*'; $index--; // it's an implicit multiplication
 208                 }
 209                 // heart of the algorithm:
 210                 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])) {
 211                     $output[] = $stack->pop(); // pop stuff off the stack into the output
 212                 }
 213                 // many thanks: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_algorithm_in_detail
 214                 $stack->push($op); // finally put OUR operator onto the stack
 215                 $index++;
 216                 $expecting_op = false;
 217             //===============
 218             } elseif ($op == ')' and $expecting_op) { // ready to close a parenthesis?
 219                 while (($o2 = $stack->pop()) != '(') { // pop off the stack back to the last (
 220                     if (is_null($o2)) return $this->trigger("unexpected ')'");
 221                     else $output[] = $o2;
 222                 }
 223                 if (preg_match("/^([a-z][a-z0-9]*)\($/", $stack->last(2), $matches)) { // did we just close a function?
 224                     $fnn = $matches[1]; // get the function name
 225                     $arg_count = $stack->pop(); // see how many arguments there were (cleverly stored on the stack, thank you)
 226                     $fn = $stack->pop();
 227                     $output[] = array('fn'=>$fn, 'fnn'=>$fnn, 'argcount'=>$arg_count); // send function to output
 228                     if (in_array($fnn, $this->fb)) { // check the argument count
 229                         if($arg_count > 1)
 230                             return $this->trigger("too many arguments ($arg_count given, 1 expected)");
 231                     } elseif (array_key_exists($fnn, $this->fc)) {
 232                         $counts = $this->fc[$fnn];
 233                         if (in_array(-1, $counts) and $arg_count > 0) {}
 234                         elseif (!in_array($arg_count, $counts))
 235                             return $this->trigger("wrong number of arguments ($arg_count given, " . implode('/',$this->fc[$fnn]) . " expected)");
 236                     } elseif (array_key_exists($fnn, $this->f)) {
 237                         if ($arg_count != count($this->f[$fnn]['args']))
 238                             return $this->trigger("wrong number of arguments ($arg_count given, " . count($this->f[$fnn]['args']) . " expected)");
 239                     } else { // did we somehow push a non-function on the stack? this should never happen
 240                         return $this->trigger("internal error");
 241                     }
 242                 }
 243                 $index++;
 244             //===============
 245             } elseif ($op == ',' and $expecting_op) { // did we just finish a function argument?
 246                 while (($o2 = $stack->pop()) != '(') {
 247                     if (is_null($o2)) return $this->trigger("unexpected ','"); // oops, never had a (
 248                     else $output[] = $o2; // pop the argument expression stuff and push onto the output
 249                 }
 250                 // make sure there was a function
 251                 if (!preg_match("/^([a-z][a-z0-9]*)\($/", $stack->last(2), $matches))
 252                     return $this->trigger("unexpected ','");
 253                 $stack->push($stack->pop()+1); // increment the argument count
 254                 $stack->push('('); // put the ( back on, we'll need to pop back to it again
 255                 $index++;
 256                 $expecting_op = false;
 257             //===============
 258             } elseif ($op == '(' and !$expecting_op) {
 259                 $stack->push('('); // that was easy
 260                 $index++;
 261                 $allow_neg = true;
 262             //===============
 263             } elseif ($ex and !$expecting_op) { // do we now have a function/variable/number?
 264                 $expecting_op = true;
 265                 $val = $match[1];
 266                 if (preg_match("/^([a-z][a-z0-9]*)\($/", $val, $matches)) { // may be func, or variable w/ implicit multiplication against parentheses...
 267                     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
 268                         $stack->push($val);
 269                         $stack->push(1);
 270                         $stack->push('(');
 271                         $expecting_op = false;
 272                     } else { // it's a var w/ implicit multiplication
 273                         $val = $matches[1];
 274                         $output[] = $val;
 275                     }
 276                 } else { // it's a plain old var or num
 277                     $output[] = $val;
 278                 }
 279                 $index += strlen($val);
 280             //===============
 281             } elseif ($op == ')') {
 282                 //it could be only custom function with no params or general error
 283                 if ($stack->last() != '(' or $stack->last(2) != 1) return $this->trigger("unexpected ')'");
 284                 if (preg_match("/^([a-z][a-z0-9]*)\($/", $stack->last(3), $matches)) { // did we just close a function?
 285                     $stack->pop();// (
 286                     $stack->pop();// 1
 287                     $fn = $stack->pop();
 288                     $fnn = $matches[1]; // get the function name
 289                     $counts = $this->fc[$fnn];
 290                     if (!in_array(0, $counts))
 291                         return $this->trigger("wrong number of arguments ($arg_count given, " . implode('/',$this->fc[$fnn]) . " expected)");
 292                     $output[] = array('fn'=>$fn, 'fnn'=>$fnn, 'argcount'=>0); // send function to output
 293                     $index++;
 294                 } else {
 295                     return $this->trigger("unexpected ')'");
 296                 }
 297             //===============
 298             } elseif (in_array($op, $ops) and !$expecting_op) { // miscellaneous error checking
 299                 return $this->trigger("unexpected operator '$op'");
 300             } else { // I don't even want to know what you did to get here
 301                 return $this->trigger("an unexpected error occured");
 302             }
 303             if ($index == strlen($expr)) {
 304                 if (in_array($op, $ops)) { // did we end with an operator? bad.
 305                     return $this->trigger("operator '$op' lacks operand");
 306                 } else {
 307                     break;
 308                 }
 309             }
 310             while (substr($expr, $index, 1) == ' ') { // step the index past whitespace (pretty much turns whitespace
 311                 $index++;                             // into implicit multiplication if no operator is there)
 312             }
 313
 314         }
 315         while (!is_null($op = $stack->pop())) { // pop everything off the stack and push onto output
 316             if ($op == '(') return $this->trigger("expecting ')'"); // if there are (s on the stack, ()s were unbalanced
 317             $output[] = $op;
 318         }
 319         return $output;
 320     }
 321
 322     // evaluate postfix notation
 323     function pfx($tokens, $vars = array()) {
 324
 325         if ($tokens == false) return false;
 326
 327         $stack = new EvalMathStack;
 328
 329         foreach ($tokens as $token) { // nice and easy
 330
 331             // if the token is a function, pop arguments off the stack, hand them to the function, and push the result back on
 332             if (is_array($token)) { // it's a function!
 333                 $fnn = $token['fnn'];
 334                 $count = $token['argcount'];
 335                 if (in_array($fnn, $this->fb)) { // built-in function:
 336                     if (is_null($op1 = $stack->pop())) return $this->trigger("internal error");
 337                     $fnn = preg_replace("/^arc/", "a", $fnn); // for the 'arc' trig synonyms
 338                     if ($fnn == 'ln') $fnn = 'log';
 339                     eval('$stack->push(' . $fnn . '($op1));'); // perfectly safe eval()
 340                 } elseif (array_key_exists($fnn, $this->fc)) { // calc emulation function
 341                     // get args
 342                     $args = array();
 343                     for ($i = $count-1; $i >= 0; $i--) {
 344                         if (is_null($args[] = $stack->pop())) return $this->trigger("internal error");
 345                     }
 346                     $res = call_user_func(array('EvalMathCalcEmul', $fnn), $args);
 347                     if ($res == FALSE) {
 348                         return $this->trigger("internal error");
 349                     }
 350                     $stack->push($res);
 351                 } elseif (array_key_exists($fnn, $this->f)) { // user function
 352                     // get args
 353                     $args = array();
 354                     for ($i = count($this->f[$fnn]['args'])-1; $i >= 0; $i--) {
 355                         if (is_null($args[$this->f[$fnn]['args'][$i]] = $stack->pop())) return $this->trigger("internal error");
 356                     }
 357                     $stack->push($this->pfx($this->f[$fnn]['func'], $args)); // yay... recursion!!!!
 358                 }
 359             // if the token is a binary operator, pop two values off the stack, do the operation, and push the result back on
 360             } elseif (in_array($token, array('+', '-', '*', '/', '^'), true)) {
 361                 if (is_null($op2 = $stack->pop())) return $this->trigger("internal error");
 362                 if (is_null($op1 = $stack->pop())) return $this->trigger("internal error");
 363                 switch ($token) {
 364                     case '+':
 365                         $stack->push($op1+$op2); break;
 366                     case '-':
 367                         $stack->push($op1-$op2); break;
 368                     case '*':
 369                         $stack->push($op1*$op2); break;
 370                     case '/':
 371                         if ($op2 == 0) return $this->trigger("division by zero");
 372                         $stack->push($op1/$op2); break;
 373                     case '^':
 374                         $stack->push(pow($op1, $op2)); break;
 375                 }
 376             // if the token is a unary operator, pop one value off the stack, do the operation, and push it back on
 377             } elseif ($token == "_") {
 378                 $stack->push(-1*$stack->pop());
 379             // if the token is a number or variable, push it on the stack
 380             } else {
 381                 if (is_numeric($token)) {
 382                     $stack->push($token);
 383                 } elseif (array_key_exists($token, $this->v)) {
 384                     $stack->push($this->v[$token]);
 385                 } elseif (array_key_exists($token, $vars)) {
 386                     $stack->push($vars[$token]);
 387                 } else {
 388                     return $this->trigger("undefined variable '$token'");
 389                 }
 390             }
 391         }
 392         // when we're out of tokens, the stack should have a single element, the final result
 393         if ($stack->count != 1) return $this->trigger("internal error");
 394         return $stack->pop();
 395     }
 396
 397     // trigger an error, but nicely, if need be
 398     function trigger($msg) {
 399         $this->last_error = $msg;
 400         if (!$this->suppress_errors) trigger_error($msg, E_USER_WARNING);
 401         return false;
 402     }
 403 }
 404
 405 // for internal use
 406 class EvalMathStack {
 407
 408     var $stack = array();
 409     var $count = 0;
 410
 411     function push($val) {
 412         $this->stack[$this->count] = $val;
 413         $this->count++;
 414     }
 415
 416     function pop() {
 417         if ($this->count > 0) {
 418             $this->count--;
 419             return $this->stack[$this->count];
 420         }
 421         return null;
 422     }
 423
 424     function last($n=1) {
 425         return $this->stack[$this->count-$n];
 426     }
 427 }
 428
 429 // spreadsheed functions emulation
 430 // watch out for reversed args!!
 431 class EvalMathCalcEmul {
 432
 433     function average($args) {
 434         return (EvalMathCalcEmul::sum($args)/count($args));
 435     }
 436
 437     function max($args) {
 438         $res = array_pop($args);
 439         foreach($args as $a) {
 440             if ($res < $a) {
 441                 $res = $a;
 442             }
 443         }
 444         return $res;
 445     }
 446
 447     function min($args) {
 448         $res = array_pop($args);
 449         foreach($args as $a) {
 450             if ($res > $a) {
 451                 $res = $a;
 452             }
 453         }
 454         return $res;
 455     }
 456
 457     function mod($args) {
 458         return $args[1] % $args[0];
 459     }
 460
 461     function pi($args) {
 462         return pi();
 463     }
 464
 465     function power($args) {
 466         return $args[1]^$args[0];
 467     }
 468
 469     function round($args) {
 470         if (count($args)==1) {
 471             return round($args[0]);
 472         } else {
 473             return round($args[1], $args[0]);
 474         }
 475     }
 476
 477     function sum($args) {
 478         $res = 0;
 479         foreach($args as $a) {
 480            $res += $a;
 481         }
 482         return $res;
 483     }
 484 }