math-expr.inc 18 KB

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