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
|
|