## root / drupal7 / sites / all / modules / ctools / includes / math-expr.inc @ 560c3060

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 |
'pow', 'exp', |

99 |
'sqrt','abs','ln','log', |

100 |
'time', 'ceil', 'floor', 'min', 'max', 'round'); |

101 | |

102 |
function ctools_math_expr() { |

103 |
// make the variables a little more accurate |

104 |
$this->v['pi'] = pi(); |

105 |
$this->v['e'] = exp(1); |

106 |
drupal_alter('ctools_math_expression_functions', $this->fb); |

107 |
} |

108 | |

109 |
function e($expr) { |

110 |
return $this->evaluate($expr); |

111 |
} |

112 | |

113 |
function evaluate($expr) { |

114 |
$this->last_error = null; |

115 |
$expr = trim($expr); |

116 |
if (substr($expr, -1, 1) == ';') $expr = substr($expr, 0, strlen($expr)-1); // strip semicolons at the end |

117 |
//=============== |

118 |
// is it a variable assignment? |

119 |
if (preg_match('/^\s*([a-z]\w*)\s*=\s*(.+)$/', $expr, $matches)) { |

120 |
if (in_array($matches[1], $this->vb)) { // make sure we're not assigning to a constant |

121 |
return $this->trigger("cannot assign to constant '$matches[1]'"); |

122 |
} |

123 |
if (($tmp = $this->pfx($this->nfx($matches[2]))) === false) return false; // get the result and make sure it's good |

124 |
$this->v[$matches[1]] = $tmp; // if so, stick it in the variable array |

125 |
return $this->v[$matches[1]]; // and return the resulting value |

126 |
//=============== |

127 |
// is it a function assignment? |

128 |
} elseif (preg_match('/^\s*([a-z]\w*)\s*\(\s*([a-z]\w*(?:\s*,\s*[a-z]\w*)*)\s*\)\s*=\s*(.+)$/', $expr, $matches)) { |

129 |
$fnn = $matches[1]; // get the function name |

130 |
if (in_array($matches[1], $this->fb)) { // make sure it isn't built in |

131 |
return $this->trigger("cannot redefine built-in function '$matches[1]()'"); |

132 |
} |

133 |
$args = explode(",", preg_replace("/\s+/", "", $matches[2])); // get the arguments |

134 |
if (($stack = $this->nfx($matches[3])) === false) return false; // see if it can be converted to postfix |

135 |
for ($i = 0; $i<count($stack); $i++) { // freeze the state of the non-argument variables |

136 |
$token = $stack[$i]; |

137 |
if (preg_match('/^[a-z]\w*$/', $token) and !in_array($token, $args)) { |

138 |
if (array_key_exists($token, $this->v)) { |

139 |
$stack[$i] = $this->v[$token]; |

140 |
} else { |

141 |
return $this->trigger("undefined variable '$token' in function definition"); |

142 |
} |

143 |
} |

144 |
} |

145 |
$this->f[$fnn] = array('args'=>$args, 'func'=>$stack); |

146 |
return true; |

147 |
//=============== |

148 |
} else { |

149 |
return $this->pfx($this->nfx($expr)); // straight up evaluation, woo |

150 |
} |

151 |
} |

152 | |

153 |
function vars() { |

154 |
$output = $this->v; |

155 |
unset($output['pi']); |

156 |
unset($output['e']); |

157 |
return $output; |

158 |
} |

159 | |

160 |
function funcs() { |

161 |
$output = array(); |

162 |
foreach ($this->f as $fnn=>$dat) |

163 |
$output[] = $fnn . '(' . implode(',', $dat['args']) . ')'; |

164 |
return $output; |

165 |
} |

166 | |

167 |
//===================== HERE BE INTERNAL METHODS ====================\\ |

168 | |

169 |
// Convert infix to postfix notation |

170 |
function nfx($expr) { |

171 | |

172 |
$index = 0; |

173 |
$stack = new ctools_math_expr_stack; |

174 |
$output = array(); // postfix form of expression, to be passed to pfx() |

175 |
$expr = trim(strtolower($expr)); |

176 | |

177 |
$ops = array('+', '-', '*', '/', '^', '_'); |

178 |
$ops_r = array('+'=>0,'-'=>0,'*'=>0,'/'=>0,'^'=>1); // right-associative operator? |

179 |
$ops_p = array('+'=>0,'-'=>0,'*'=>1,'/'=>1,'_'=>1,'^'=>2); // operator precedence |

180 | |

181 |
$expecting_op = false; // we use this in syntax-checking the expression |

182 |
// and determining when a - is a negation |

183 | |

184 |
if (preg_match("/[^\w\s+*^\/()\.,-]/", $expr, $matches)) { // make sure the characters are all good |

185 |
return $this->trigger("illegal character '{$matches[0]}'"); |

186 |
} |

187 | |

188 |
while(1) { // 1 Infinite Loop ;) |

189 |
$op = substr($expr, $index, 1); // get the first character at the current index |

190 |
// find out if we're currently at the beginning of a number/variable/function/parenthesis/operand |

191 |
$ex = preg_match('/^([a-z]\w*\(?|\d+(?:\.\d*)?|\.\d+|\()/', substr($expr, $index), $match); |

192 |
//=============== |

193 |
if ($op == '-' and !$expecting_op) { // is it a negation instead of a minus? |

194 |
$stack->push('_'); // put a negation on the stack |

195 |
$index++; |

196 |
} elseif ($op == '_') { // we have to explicitly deny this, because it's legal on the stack |

197 |
return $this->trigger("illegal character '_'"); // but not in the input expression |

198 |
//=============== |

199 |
} elseif ((in_array($op, $ops) or $ex) and $expecting_op) { // are we putting an operator on the stack? |

200 |
if ($ex) { // are we expecting an operator but have a number/variable/function/opening parethesis? |

201 |
$op = '*'; $index--; // it's an implicit multiplication |

202 |
} |

203 |
// heart of the algorithm: |

204 |
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])) { |

205 |
$output[] = $stack->pop(); // pop stuff off the stack into the output |

206 |
} |

207 |
// many thanks: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_algorithm_in_detail |

208 |
$stack->push($op); // finally put OUR operator onto the stack |

209 |
$index++; |

210 |
$expecting_op = false; |

211 |
//=============== |

212 |
} elseif ($op == ')' and $expecting_op) { // ready to close a parenthesis? |

213 |
while (($o2 = $stack->pop()) != '(') { // pop off the stack back to the last ( |

214 |
if (is_null($o2)) return $this->trigger("unexpected ')'"); |

215 |
else $output[] = $o2; |

216 |
} |

217 |
if (preg_match("/^([a-z]\w*)\($/", $stack->last(2), $matches)) { // did we just close a function? |

218 |
$fnn = $matches[1]; // get the function name |

219 |
$arg_count = $stack->pop(); // see how many arguments there were (cleverly stored on the stack, thank you) |

220 |
$output[] = $stack->pop(); // pop the function and push onto the output |

221 |
if (in_array($fnn, $this->fb)) { // check the argument count |

222 |
if($arg_count > 1) |

223 |
return $this->trigger("too many arguments ($arg_count given, 1 expected)"); |

224 |
} elseif (array_key_exists($fnn, $this->f)) { |

225 |
if ($arg_count != count($this->f[$fnn]['args'])) |

226 |
return $this->trigger("wrong number of arguments ($arg_count given, " . count($this->f[$fnn]['args']) . " expected)"); |

227 |
} else { // did we somehow push a non-function on the stack? this should never happen |

228 |
return $this->trigger("internal error"); |

229 |
} |

230 |
} |

231 |
$index++; |

232 |
//=============== |

233 |
} elseif ($op == ',' and $expecting_op) { // did we just finish a function argument? |

234 |
while (($o2 = $stack->pop()) != '(') { |

235 |
if (is_null($o2)) return $this->trigger("unexpected ','"); // oops, never had a ( |

236 |
else $output[] = $o2; // pop the argument expression stuff and push onto the output |

237 |
} |

238 |
// make sure there was a function |

239 |
if (!preg_match("/^([a-z]\w*)\($/", $stack->last(2), $matches)) |

240 |
return $this->trigger("unexpected ','"); |

241 |
$stack->push($stack->pop()+1); // increment the argument count |

242 |
$stack->push('('); // put the ( back on, we'll need to pop back to it again |

243 |
$index++; |

244 |
$expecting_op = false; |

245 |
//=============== |

246 |
} elseif ($op == '(' and !$expecting_op) { |

247 |
$stack->push('('); // that was easy |

248 |
$index++; |

249 |
$allow_neg = true; |

250 |
//=============== |

251 |
} elseif ($ex and !$expecting_op) { // do we now have a function/variable/number? |

252 |
$expecting_op = true; |

253 |
$val = $match[1]; |

254 |
if (preg_match("/^([a-z]\w*)\($/", $val, $matches)) { // may be func, or variable w/ implicit multiplication against parentheses... |

255 |
if (in_array($matches[1], $this->fb) or array_key_exists($matches[1], $this->f)) { // it's a func |

256 |
$stack->push($val); |

257 |
$stack->push(1); |

258 |
$stack->push('('); |

259 |
$expecting_op = false; |

260 |
} else { // it's a var w/ implicit multiplication |

261 |
$val = $matches[1]; |

262 |
$output[] = $val; |

263 |
} |

264 |
} else { // it's a plain old var or num |

265 |
$output[] = $val; |

266 |
} |

267 |
$index += strlen($val); |

268 |
//=============== |

269 |
} elseif ($op == ')') { // miscellaneous error checking |

270 |
return $this->trigger("unexpected ')'"); |

271 |
} elseif (in_array($op, $ops) and !$expecting_op) { |

272 |
return $this->trigger("unexpected operator '$op'"); |

273 |
} else { // I don't even want to know what you did to get here |

274 |
return $this->trigger("an unexpected error occurred"); |

275 |
} |

276 |
if ($index == strlen($expr)) { |

277 |
if (in_array($op, $ops)) { // did we end with an operator? bad. |

278 |
return $this->trigger("operator '$op' lacks operand"); |

279 |
} else { |

280 |
break; |

281 |
} |

282 |
} |

283 |
while (substr($expr, $index, 1) == ' ') { // step the index past whitespace (pretty much turns whitespace |

284 |
$index++; // into implicit multiplication if no operator is there) |

285 |
} |

286 | |

287 |
} |

288 |
while (!is_null($op = $stack->pop())) { // pop everything off the stack and push onto output |

289 |
if ($op == '(') return $this->trigger("expecting ')'"); // if there are (s on the stack, ()s were unbalanced |

290 |
$output[] = $op; |

291 |
} |

292 |
return $output; |

293 |
} |

294 | |

295 |
// evaluate postfix notation |

296 |
function pfx($tokens, $vars = array()) { |

297 | |

298 |
if ($tokens == false) return false; |

299 | |

300 |
$stack = new ctools_math_expr_stack; |

301 | |

302 |
foreach ($tokens as $token) { // nice and easy |

303 |
// if the token is a binary operator, pop two values off the stack, do the operation, and push the result back on |

304 |
if (in_array($token, array('+', '-', '*', '/', '^'))) { |

305 |
if (is_null($op2 = $stack->pop())) return $this->trigger("internal error"); |

306 |
if (is_null($op1 = $stack->pop())) return $this->trigger("internal error"); |

307 |
switch ($token) { |

308 |
case '+': |

309 |
$stack->push($op1+$op2); break; |

310 |
case '-': |

311 |
$stack->push($op1-$op2); break; |

312 |
case '*': |

313 |
$stack->push($op1*$op2); break; |

314 |
case '/': |

315 |
if ($op2 == 0) return $this->trigger("division by zero"); |

316 |
$stack->push($op1/$op2); break; |

317 |
case '^': |

318 |
$stack->push(pow($op1, $op2)); break; |

319 |
} |

320 |
// if the token is a unary operator, pop one value off the stack, do the operation, and push it back on |

321 |
} elseif ($token == "_") { |

322 |
$stack->push(-1*$stack->pop()); |

323 |
// if the token is a function, pop arguments off the stack, hand them to the function, and push the result back on |

324 |
} elseif (preg_match("/^([a-z]\w*)\($/", $token, $matches)) { // it's a function! |

325 |
$fnn = $matches[1]; |

326 |
if (in_array($fnn, $this->fb)) { // built-in function: |

327 |
if (is_null($op1 = $stack->pop())) return $this->trigger("internal error"); |

328 |
$fnn = preg_replace("/^arc/", "a", $fnn); // for the 'arc' trig synonyms |

329 |
if ($fnn == 'ln') $fnn = 'log'; |

330 |
eval('$stack->push(' . $fnn . '($op1));'); // perfectly safe eval() |

331 |
} elseif (array_key_exists($fnn, $this->f)) { // user function |

332 |
// get args |

333 |
$args = array(); |

334 |
for ($i = count($this->f[$fnn]['args'])-1; $i >= 0; $i--) { |

335 |
if (is_null($args[$this->f[$fnn]['args'][$i]] = $stack->pop())) return $this->trigger("internal error"); |

336 |
} |

337 |
$stack->push($this->pfx($this->f[$fnn]['func'], $args)); // yay... recursion!!!! |

338 |
} |

339 |
// if the token is a number or variable, push it on the stack |

340 |
} else { |

341 |
if (is_numeric($token)) { |

342 |
$stack->push($token); |

343 |
} elseif (array_key_exists($token, $this->v)) { |

344 |
$stack->push($this->v[$token]); |

345 |
} elseif (array_key_exists($token, $vars)) { |

346 |
$stack->push($vars[$token]); |

347 |
} else { |

348 |
return $this->trigger("undefined variable '$token'"); |

349 |
} |

350 |
} |

351 |
} |

352 |
// when we're out of tokens, the stack should have a single element, the final result |

353 |
if ($stack->count != 1) return $this->trigger("internal error"); |

354 |
return $stack->pop(); |

355 |
} |

356 | |

357 |
// trigger an error, but nicely, if need be |

358 |
function trigger($msg) { |

359 |
$this->last_error = $msg; |

360 |
if (!$this->suppress_errors) trigger_error($msg, E_USER_WARNING); |

361 |
return false; |

362 |
} |

363 |
} |

364 | |

365 |
// for internal use |

366 |
class ctools_math_expr_stack { |

367 | |

368 |
var $stack = array(); |

369 |
var $count = 0; |

370 | |

371 |
function push($val) { |

372 |
$this->stack[$this->count] = $val; |

373 |
$this->count++; |

374 |
} |

375 | |

376 |
function pop() { |

377 |
if ($this->count > 0) { |

378 |
$this->count--; |

379 |
return $this->stack[$this->count]; |

380 |
} |

381 |
return null; |

382 |
} |

383 | |

384 |
function last($n=1) { |

385 |
return !empty($this->stack[$this->count-$n]) ? $this->stack[$this->count-$n] : NULL; |

386 |
} |

387 |
} |

388 |