Project

General

Profile

Paste
Download (17.7 KB) Statistics
| Branch: | Revision:

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