[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /*
   4  ================================================================================
   5  
   6  ctools_math_expr - PHP Class to safely evaluate math expressions
   7  Copyright (C) 2005 Miles Kaufmann <http://www.twmagic.com/>
   8  
   9  ================================================================================
  10  
  11  NAME
  12      ctools_math_expr - safely evaluate math expressions
  13  
  14  SYNOPSIS
  15        include('ctools_math_expr.class.php');
  16        $m = new ctools_math_expr;
  17        // basic evaluation:
  18        $result = $m->evaluate('2+2');
  19        // supports: order of operation; parentheses; negation; built-in functions
  20        $result = $m->evaluate('-8(5/2)^2*(1-sqrt(4))-8');
  21        // create your own variables
  22        $m->evaluate('a = e^(ln(pi))');
  23        // or functions
  24        $m->evaluate('f(x,y) = x^2 + y^2 - 2x*y + 1');
  25        // and then use them
  26        $result = $m->evaluate('3*f(42,a)');
  27  
  28  DESCRIPTION
  29      Use the ctools_math_expr class when you want to evaluate mathematical expressions
  30      from untrusted sources.  You can define your own variables and functions,
  31      which are stored in the object.  Try it, it's fun!
  32  
  33  METHODS
  34      $m->evalute($expr)
  35          Evaluates the expression and returns the result.  If an error occurs,
  36          prints a warning and returns false.  If $expr is a function assignment,
  37          returns true on success.
  38  
  39      $m->e($expr)
  40          A synonym for $m->evaluate().
  41  
  42      $m->vars()
  43          Returns an associative array of all user-defined variables and values.
  44  
  45      $m->funcs()
  46          Returns an array of all user-defined functions.
  47  
  48  PARAMETERS
  49      $m->suppress_errors
  50          Set to true to turn off warnings when evaluating expressions
  51  
  52      $m->last_error
  53          If the last evaluation failed, contains a string describing the error.
  54          (Useful when suppress_errors is on).
  55  
  56  AUTHOR INFORMATION
  57      Copyright 2005, Miles Kaufmann.
  58  
  59  LICENSE
  60      Redistribution and use in source and binary forms, with or without
  61      modification, are permitted provided that the following conditions are
  62      met:
  63  
  64      1   Redistributions of source code must retain the above copyright
  65          notice, this list of conditions and the following disclaimer.
  66      2.  Redistributions in binary form must reproduce the above copyright
  67          notice, this list of conditions and the following disclaimer in the
  68          documentation and/or other materials provided with the distribution.
  69      3.  The name of the author may not be used to endorse or promote
  70          products derived from this software without specific prior written
  71          permission.
  72  
  73      THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  74      IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  75      WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  76      DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  77      INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  78      (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  79      SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  80      HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  81      STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  82      ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  83      POSSIBILITY OF SUCH DAMAGE.
  84  
  85  */
  86  
  87  class ctools_math_expr {
  88      var $suppress_errors = false;
  89      var $last_error = null;
  90  
  91      var $v = array('e'=>2.71,'pi'=>3.14); // variables (and constants)
  92      var $f = array(); // user-defined functions
  93      var $vb = array('e', 'pi'); // constants
  94      var $fb = array(  // built-in functions
  95          'sin','sinh','arcsin','asin','arcsinh','asinh',
  96          'cos','cosh','arccos','acos','arccosh','acosh',
  97          'tan','tanh','arctan','atan','arctanh','atanh',
  98          'sqrt','abs','ln','log');
  99  
 100      function ctools_math_expr() {
 101          // make the variables a little more accurate
 102          $this->v['pi'] = pi();
 103          $this->v['e'] = exp(1);
 104      }
 105  
 106      function e($expr) {
 107          return $this->evaluate($expr);
 108      }
 109  
 110      function evaluate($expr) {
 111          $this->last_error = null;
 112          $expr = trim($expr);
 113          if (substr($expr, -1, 1) == ';') $expr = substr($expr, 0, strlen($expr)-1); // strip semicolons at the end
 114          //===============
 115          // is it a variable assignment?
 116          if (preg_match('/^\s*([a-z]\w*)\s*=\s*(.+)$/', $expr, $matches)) {
 117              if (in_array($matches[1], $this->vb)) { // make sure we're not assigning to a constant
 118                  return $this->trigger("cannot assign to constant '$matches[1]'");
 119              }
 120              if (($tmp = $this->pfx($this->nfx($matches[2]))) === false) return false; // get the result and make sure it's good
 121              $this->v[$matches[1]] = $tmp; // if so, stick it in the variable array
 122              return $this->v[$matches[1]]; // and return the resulting value
 123          //===============
 124          // is it a function assignment?
 125          } elseif (preg_match('/^\s*([a-z]\w*)\s*\(\s*([a-z]\w*(?:\s*,\s*[a-z]\w*)*)\s*\)\s*=\s*(.+)$/', $expr, $matches)) {
 126              $fnn = $matches[1]; // get the function name
 127              if (in_array($matches[1], $this->fb)) { // make sure it isn't built in
 128                  return $this->trigger("cannot redefine built-in function '$matches[1]()'");
 129              }
 130              $args = explode(",", preg_replace("/\s+/", "", $matches[2])); // get the arguments
 131              if (($stack = $this->nfx($matches[3])) === false) return false; // see if it can be converted to postfix
 132              for ($i = 0; $i<count($stack); $i++) { // freeze the state of the non-argument variables
 133                  $token = $stack[$i];
 134                  if (preg_match('/^[a-z]\w*$/', $token) and !in_array($token, $args)) {
 135                      if (array_key_exists($token, $this->v)) {
 136                          $stack[$i] = $this->v[$token];
 137                      } else {
 138                          return $this->trigger("undefined variable '$token' in function definition");
 139                      }
 140                  }
 141              }
 142              $this->f[$fnn] = array('args'=>$args, 'func'=>$stack);
 143              return true;
 144          //===============
 145          } else {
 146              return $this->pfx($this->nfx($expr)); // straight up evaluation, woo
 147          }
 148      }
 149  
 150      function vars() {
 151          $output = $this->v;
 152          unset($output['pi']);
 153          unset($output['e']);
 154          return $output;
 155      }
 156  
 157      function funcs() {
 158          $output = array();
 159          foreach ($this->f as $fnn=>$dat)
 160              $output[] = $fnn . '(' . implode(',', $dat['args']) . ')';
 161          return $output;
 162      }
 163  
 164      //===================== HERE BE INTERNAL METHODS ====================\\
 165  
 166      // Convert infix to postfix notation
 167      function nfx($expr) {
 168  
 169          $index = 0;
 170          $stack = new ctools_math_expr_stack;
 171          $output = array(); // postfix form of expression, to be passed to pfx()
 172          $expr = trim(strtolower($expr));
 173  
 174          $ops   = array('+', '-', '*', '/', '^', '_');
 175          $ops_r = array('+'=>0,'-'=>0,'*'=>0,'/'=>0,'^'=>1); // right-associative operator?
 176          $ops_p = array('+'=>0,'-'=>0,'*'=>1,'/'=>1,'_'=>1,'^'=>2); // operator precedence
 177  
 178          $expecting_op = false; // we use this in syntax-checking the expression
 179                                 // and determining when a - is a negation
 180  
 181          if (preg_match("/[^\w\s+*^\/()\.,-]/", $expr, $matches)) { // make sure the characters are all good
 182              return $this->trigger("illegal character '{$matches[0]}'");
 183          }
 184  
 185          while(1) { // 1 Infinite Loop ;)
 186              $op = substr($expr, $index, 1); // get the first character at the current index
 187              // find out if we're currently at the beginning of a number/variable/function/parenthesis/operand
 188              $ex = preg_match('/^([a-z]\w*\(?|\d+(?:\.\d*)?|\.\d+|\()/', substr($expr, $index), $match);
 189              //===============
 190              if ($op == '-' and !$expecting_op) { // is it a negation instead of a minus?
 191                  $stack->push('_'); // put a negation on the stack
 192                  $index++;
 193              } elseif ($op == '_') { // we have to explicitly deny this, because it's legal on the stack
 194                  return $this->trigger("illegal character '_'"); // but not in the input expression
 195              //===============
 196              } elseif ((in_array($op, $ops) or $ex) and $expecting_op) { // are we putting an operator on the stack?
 197                  if ($ex) { // are we expecting an operator but have a number/variable/function/opening parethesis?
 198                      $op = '*'; $index--; // it's an implicit multiplication
 199                  }
 200                  // heart of the algorithm:
 201                  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])) {
 202                      $output[] = $stack->pop(); // pop stuff off the stack into the output
 203                  }
 204                  // many thanks: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_algorithm_in_detail
 205                  $stack->push($op); // finally put OUR operator onto the stack
 206                  $index++;
 207                  $expecting_op = false;
 208              //===============
 209              } elseif ($op == ')' and $expecting_op) { // ready to close a parenthesis?
 210                  while (($o2 = $stack->pop()) != '(') { // pop off the stack back to the last (
 211                      if (is_null($o2)) return $this->trigger("unexpected ')'");
 212                      else $output[] = $o2;
 213                  }
 214                  if (preg_match("/^([a-z]\w*)\($/", $stack->last(2), $matches)) { // did we just close a function?
 215                      $fnn = $matches[1]; // get the function name
 216                      $arg_count = $stack->pop(); // see how many arguments there were (cleverly stored on the stack, thank you)
 217                      $output[] = $stack->pop(); // pop the function and push onto the output
 218                      if (in_array($fnn, $this->fb)) { // check the argument count
 219                          if($arg_count > 1)
 220                              return $this->trigger("too many arguments ($arg_count given, 1 expected)");
 221                      } elseif (array_key_exists($fnn, $this->f)) {
 222                          if ($arg_count != count($this->f[$fnn]['args']))
 223                              return $this->trigger("wrong number of arguments ($arg_count given, " . count($this->f[$fnn]['args']) . " expected)");
 224                      } else { // did we somehow push a non-function on the stack? this should never happen
 225                          return $this->trigger("internal error");
 226                      }
 227                  }
 228                  $index++;
 229              //===============
 230              } elseif ($op == ',' and $expecting_op) { // did we just finish a function argument?
 231                  while (($o2 = $stack->pop()) != '(') {
 232                      if (is_null($o2)) return $this->trigger("unexpected ','"); // oops, never had a (
 233                      else $output[] = $o2; // pop the argument expression stuff and push onto the output
 234                  }
 235                  // make sure there was a function
 236                  if (!preg_match("/^([a-z]\w*)\($/", $stack->last(2), $matches))
 237                      return $this->trigger("unexpected ','");
 238                  $stack->push($stack->pop()+1); // increment the argument count
 239                  $stack->push('('); // put the ( back on, we'll need to pop back to it again
 240                  $index++;
 241                  $expecting_op = false;
 242              //===============
 243              } elseif ($op == '(' and !$expecting_op) {
 244                  $stack->push('('); // that was easy
 245                  $index++;
 246                  $allow_neg = true;
 247              //===============
 248              } elseif ($ex and !$expecting_op) { // do we now have a function/variable/number?
 249                  $expecting_op = true;
 250                  $val = $match[1];
 251                  if (preg_match("/^([a-z]\w*)\($/", $val, $matches)) { // may be func, or variable w/ implicit multiplication against parentheses...
 252                      if (in_array($matches[1], $this->fb) or array_key_exists($matches[1], $this->f)) { // it's a func
 253                          $stack->push($val);
 254                          $stack->push(1);
 255                          $stack->push('(');
 256                          $expecting_op = false;
 257                      } else { // it's a var w/ implicit multiplication
 258                          $val = $matches[1];
 259                          $output[] = $val;
 260                      }
 261                  } else { // it's a plain old var or num
 262                      $output[] = $val;
 263                  }
 264                  $index += strlen($val);
 265              //===============
 266              } elseif ($op == ')') { // miscellaneous error checking
 267                  return $this->trigger("unexpected ')'");
 268              } elseif (in_array($op, $ops) and !$expecting_op) {
 269                  return $this->trigger("unexpected operator '$op'");
 270              } else { // I don't even want to know what you did to get here
 271                  return $this->trigger("an unexpected error occured");
 272              }
 273              if ($index == strlen($expr)) {
 274                  if (in_array($op, $ops)) { // did we end with an operator? bad.
 275                      return $this->trigger("operator '$op' lacks operand");
 276                  } else {
 277                      break;
 278                  }
 279              }
 280              while (substr($expr, $index, 1) == ' ') { // step the index past whitespace (pretty much turns whitespace
 281                  $index++;                             // into implicit multiplication if no operator is there)
 282              }
 283  
 284          }
 285          while (!is_null($op = $stack->pop())) { // pop everything off the stack and push onto output
 286              if ($op == '(') return $this->trigger("expecting ')'"); // if there are (s on the stack, ()s were unbalanced
 287              $output[] = $op;
 288          }
 289          return $output;
 290      }
 291  
 292      // evaluate postfix notation
 293      function pfx($tokens, $vars = array()) {
 294  
 295          if ($tokens == false) return false;
 296  
 297          $stack = new ctools_math_expr_stack;
 298  
 299          foreach ($tokens as $token) { // nice and easy
 300              // if the token is a binary operator, pop two values off the stack, do the operation, and push the result back on
 301              if (in_array($token, array('+', '-', '*', '/', '^'))) {
 302                  if (is_null($op2 = $stack->pop())) return $this->trigger("internal error");
 303                  if (is_null($op1 = $stack->pop())) return $this->trigger("internal error");
 304                  switch ($token) {
 305                      case '+':
 306                          $stack->push($op1+$op2); break;
 307                      case '-':
 308                          $stack->push($op1-$op2); break;
 309                      case '*':
 310                          $stack->push($op1*$op2); break;
 311                      case '/':
 312                          if ($op2 == 0) return $this->trigger("division by zero");
 313                          $stack->push($op1/$op2); break;
 314                      case '^':
 315                          $stack->push(pow($op1, $op2)); break;
 316                  }
 317              // if the token is a unary operator, pop one value off the stack, do the operation, and push it back on
 318              } elseif ($token == "_") {
 319                  $stack->push(-1*$stack->pop());
 320              // if the token is a function, pop arguments off the stack, hand them to the function, and push the result back on
 321              } elseif (preg_match("/^([a-z]\w*)\($/", $token, $matches)) { // it's a function!
 322                  $fnn = $matches[1];
 323                  if (in_array($fnn, $this->fb)) { // built-in function:
 324                      if (is_null($op1 = $stack->pop())) return $this->trigger("internal error");
 325                      $fnn = preg_replace("/^arc/", "a", $fnn); // for the 'arc' trig synonyms
 326                      if ($fnn == 'ln') $fnn = 'log';
 327                      eval('$stack->push(' . $fnn . '($op1));'); // perfectly safe eval()
 328                  } elseif (array_key_exists($fnn, $this->f)) { // user function
 329                      // get args
 330                      $args = array();
 331                      for ($i = count($this->f[$fnn]['args'])-1; $i >= 0; $i--) {
 332                          if (is_null($args[$this->f[$fnn]['args'][$i]] = $stack->pop())) return $this->trigger("internal error");
 333                      }
 334                      $stack->push($this->pfx($this->f[$fnn]['func'], $args)); // yay... recursion!!!!
 335                  }
 336              // if the token is a number or variable, push it on the stack
 337              } else {
 338                  if (is_numeric($token)) {
 339                      $stack->push($token);
 340                  } elseif (array_key_exists($token, $this->v)) {
 341                      $stack->push($this->v[$token]);
 342                  } elseif (array_key_exists($token, $vars)) {
 343                      $stack->push($vars[$token]);
 344                  } else {
 345                      return $this->trigger("undefined variable '$token'");
 346                  }
 347              }
 348          }
 349          // when we're out of tokens, the stack should have a single element, the final result
 350          if ($stack->count != 1) return $this->trigger("internal error");
 351          return $stack->pop();
 352      }
 353  
 354      // trigger an error, but nicely, if need be
 355      function trigger($msg) {
 356          $this->last_error = $msg;
 357          if (!$this->suppress_errors) trigger_error($msg, E_USER_WARNING);
 358          return false;
 359      }
 360  }
 361  
 362  // for internal use
 363  class ctools_math_expr_stack {
 364  
 365      var $stack = array();
 366      var $count = 0;
 367  
 368      function push($val) {
 369          $this->stack[$this->count] = $val;
 370          $this->count++;
 371      }
 372  
 373      function pop() {
 374          if ($this->count > 0) {
 375              $this->count--;
 376              return $this->stack[$this->count];
 377          }
 378          return null;
 379      }
 380  
 381      function last($n=1) {
 382          return !empty($this->stack[$this->count-$n]) ? $this->stack[$this->count-$n] : NULL;
 383      }
 384  }
 385