Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php // This is a set of functions to solve mathematical terms ("3 + 3 * 2").
- // - The current version supports brackets and function calls but no
- // negative numbers. Use "(0-3)" instead of "-3".
- // - Expect errors.
- // The code is public domain. Original author: http://www.ermshaus.org/
- /**
- *
- *
- * The lower the index, the higher (!) the precedence
- *
- * @staticvar string $pre
- * @return array
- */
- function getOperatorPrecedenceTable()
- {
- /** @todo Supposed to be a cache. Code really needs OOP */
- static $pre = null;
- if ($pre === null) {
- $precedence = array(
- array('*', '/', '%'),
- array('+', '-')
- );
- $tmp = array();
- foreach ($precedence as $weight => $row) {
- foreach ($row as $item) {
- $tmp[$item] = $weight;
- }
- }
- $pre = $tmp;
- }
- return $pre;
- }
- /**
- * Splits the input into logical tokens
- *
- * e. g. "(3 + 4) * 2" => array("(", "3", "+", "4", ")", "*", "2")
- *
- * @param string $input
- * @return array
- */
- function tokenize($input)
- {
- $temp = preg_split('/(\d+(?:\.\d+)?) | ([*\/%+,()-]) | ([a-z]+)/isx',
- $input, null, PREG_SPLIT_NO_EMPTY | PREG_SPLIT_DELIM_CAPTURE);
- $tokens = array();
- foreach ($temp as $t) {
- if (trim($t) !== '') {
- $tokens[] = trim($t);
- }
- }
- return $tokens;
- }
- /**
- *
- *
- * @todo God function
- *
- * @staticvar array $funcs
- * @param array $tokens
- * @param array $precedences
- * @return array
- */
- function buildAst(array $tokens, array $precedences)
- {
- /** @todo Supposed to be a cache. Code really needs OOP */
- static $funcs = array(
- '*' => 'mul', '/' => 'div', '%' => 'mod',
- '+' => 'add', '-' => 'sub');
- // Single scalar value?
- if (count($tokens) === 1) {
- return $tokens;
- }
- // Functions? (e. g. sqrt, min, max, ...)
- $f = function ($a) {
- $ret = false;
- foreach ($a as $e) {
- if (!is_array($e) && preg_match('/[a-z]+/i', $e) === 1) {
- $ret = true;
- break;
- }
- }
- return $ret;
- };
- while ($f($tokens)) {
- $firstOpeningBracketIndex = -1;
- $matchingClosingBracketIndex = -1;
- $functionPos = -1;
- $bracketCount = 0;
- foreach ($tokens as $index => $token) {
- if ($functionPos === -1) {
- if (!is_array($token)
- && preg_match('/[a-z]+/i', $token) === 1
- ) {
- $functionPos = $index;
- }
- } else {
- if ($token === '(') {
- if ($firstOpeningBracketIndex === -1) {
- $firstOpeningBracketIndex = $index;
- }
- $bracketCount++;
- } else if ($token === ')') {
- $bracketCount--;
- if ($bracketCount < 0) {
- throw new Exception('Too many closing brackets');
- }
- if ($bracketCount === 0) {
- $matchingClosingBracketIndex = $index;
- break;
- }
- }
- }
- }
- if ($matchingClosingBracketIndex === -1) {
- throw new Exception('Too many opening brackets');
- }
- // construct Sub-AST
- $subTokenList = array_slice($tokens,
- $firstOpeningBracketIndex + 1,
- $matchingClosingBracketIndex - $firstOpeningBracketIndex - 1);
- $parts = array();
- $partsTemp = array();
- $brackCount = 0;
- // Generate a sub tree for each parameter (a, b in "f(a, b)")
- while (count($subTokenList) > 0) {
- $first = array_shift($subTokenList);
- if ($first === ',' && $brackCount === 0) {
- $parts[] = $partsTemp;
- $partsTemp = array();
- } else {
- if ($first === '(') {
- $brackCount++;
- } else if ($first === ')') {
- $brackCount--;
- }
- $partsTemp[] = $first;
- }
- }
- $parts[] = $partsTemp;
- $subAst = array();
- foreach ($parts as $part) {
- $subAstTemp = buildAst($part, $precedences);
- /** @todo See corresponding todo item below */
- if (count($subAstTemp) === 1) {
- $subAstTemp = $subAstTemp[0];
- }
- $subAst[] = $subAstTemp;
- }
- array_unshift($subAst, $tokens[$functionPos]);
- array_splice($tokens,
- $firstOpeningBracketIndex - 1,
- $matchingClosingBracketIndex - $firstOpeningBracketIndex + 2,
- array($subAst));
- }
- // Brackets?
- while (in_array('(', $tokens)) {
- $firstOpeningBracketIndex = -1;
- $matchingClosingBracketIndex = -1;
- $bracketCount = 0;
- foreach ($tokens as $index => $token) {
- if ($token === '(') {
- if ($firstOpeningBracketIndex === -1) {
- $firstOpeningBracketIndex = $index;
- }
- $bracketCount++;
- } else if ($token === ')') {
- $bracketCount--;
- if ($bracketCount < 0) {
- throw new Exception('Too many closing brackets');
- }
- if ($bracketCount === 0) {
- $matchingClosingBracketIndex = $index;
- break;
- }
- }
- }
- if ($matchingClosingBracketIndex === -1) {
- throw new Exception('Too many opening brackets');
- }
- // construct Sub-AST
- $subAst = buildAst(
- array_slice(
- $tokens,
- $firstOpeningBracketIndex + 1,
- $matchingClosingBracketIndex - $firstOpeningBracketIndex - 1
- ), $precedences);
- /** @todo This is needed to fix an issue with single function calls in
- * brackets "(min(1,2))"
- */
- if (count($subAst) === 1) {
- $subAst = $subAst[0];
- }
- array_splice($tokens,
- $firstOpeningBracketIndex,
- $matchingClosingBracketIndex - $firstOpeningBracketIndex + 1,
- array($subAst));
- }
- // Finally, process operators (+, -, ...)
- do {
- $n = -1;
- foreach ($tokens as $i => $item) {
- if (!is_array($item) && !is_numeric($item)) {
- if ($n === -1
- || $precedences[$item] < $precedences[$tokens[$n]]
- ) {
- $n = $i;
- }
- }
- }
- if ($n > -1) {
- /** @todo We could probably do something more clever than throwing
- * exceptions
- * (e. g. left padding "-" with "-1 *" and "+" with "0 +")
- */
- if ($n === 0) {
- throw new Exception('No left operand available before "'
- . $tokens[$n] . '"');
- }
- if ($n === count($tokens) - 1) {
- throw new Exception('No right operand available after "'
- . $tokens[$n] . '"');
- }
- // Function/operator name is always first entry
- $repl = array($funcs[$tokens[$n]], $tokens[$n - 1],
- $tokens[$n + 1]);
- array_splice($tokens, $n - 1, 3, array($repl));
- }
- } while ($n > -1);
- return $tokens[0];
- }
- /**
- * Returns a debug string of the generated parse tree
- *
- * @param array $ast
- * @return string
- */
- function printAst(array $ast)
- {
- $s = '';
- $cnt = count($ast);
- if ($cnt === 1) {
- return $ast[0];
- }
- $s .= $ast[0] . '(';
- for ($i = 1; $i < $cnt; $i++) {
- $item = $ast[$i];
- if (is_array($item)) {
- $s .= printAst($item);
- } else {
- $s .= $item;
- }
- $s .= ', ';
- }
- $s = rtrim(trim($s), ',') . ')';
- return $s;
- }
- /**
- *
- * @param array $ast
- * @return mixed The result of the input term
- */
- function solveAst(array $ast)
- {
- $s = '';
- $cnt = count($ast);
- if ($cnt === 1) {
- return $ast[0];
- }
- $op = $ast[0];
- $params = array();
- for ($i = 1; $i < $cnt; $i++) {
- $item = $ast[$i];
- if (is_array($item)) {
- $params[] = solveAst($item);
- } else {
- $params[] = $item;
- }
- }
- $res = 0;
- /** @todo Superfluous parameters shouldn't be silently discarded */
- switch (strtolower($op)) {
- case 'mul':
- $res = $params[0] * $params[1];
- break;
- case 'div':
- $res = $params[0] / $params[1];
- break;
- case 'mod':
- $res = $params[0] % $params[1];
- break;
- case 'add':
- $res = $params[0] + $params[1];
- break;
- case 'sub':
- $res = $params[0] - $params[1];
- break;
- case 'sqrt':
- $res = sqrt($params[0]);
- break;
- case 'max':
- $res = max($params);
- break;
- case 'min':
- $res = min($params);
- break;
- default:
- throw new Exception('Unknown operation: ' . $op);
- break;
- }
- return $res;
- }
- error_reporting(-1);
- $input = '(5 + 2) + ((7)) + (min(3, 2)) * (max(19, 32, 45 + 9, max(2, 3, 499.5)) + sqrt(45 - 9) * 7 / 2 + 21)';
- #$input = '6 % (7 * (7 + 21) - 5) *19 + 45 - 2';
- #$input = '7';
- $tokens = tokenize($input);
- echo implode(' ', $tokens), "\n\n\n";
- $precedences = getOperatorPrecedenceTable();
- $ast = buildAst($tokens, $precedences);
- echo printAst($ast), "\n\n\n";
- $result = solveAst($ast);
- echo 'Result: ' . $result, "\n\n\n";
- echo 'eval\'d result: ';
- eval('echo ' . $input . ';');
- echo "\n\n\n";
- echo "\n";
- // Example output:
- /*
- ( 5 + 2 ) + ( ( 7 ) ) + ( min ( 3 , 2 ) ) * ( max ( 19
- , 32 , 45 + 9 , max ( 2 , 3 , 499.5 ) ) + sqrt ( 45 - 9 )
- * 7 / 2 + 21 )
- add(add(add(5, 2), 7), mul(min(3, 2), add(add(max(19, 32, add(45, 9),
- max(2, 3, 499.5)), div(mul(sqrt(sub(45, 9)), 7), 2)), 21)))
- Result: 1097
- eval'd result: 1097
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement