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