Guest User

Untitled

a guest
May 31st, 2011
180
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php // This is a set of functions to solve mathematical terms ("3 + 3 * 2").
  2.       // - The current version supports brackets and function calls but no
  3.       //   negative numbers. Use "(0-3)" instead of "-3".
  4.       // - Expect errors.
  5.       // The code is public domain. Original author: http://www.ermshaus.org/
  6.  
  7. /**
  8.  *
  9.  *
  10.  * The lower the index, the higher (!) the precedence
  11.  *
  12.  * @staticvar string $pre
  13.  * @return array
  14.  */
  15. function getOperatorPrecedenceTable()
  16. {
  17.     /** @todo Supposed to be a cache. Code really needs OOP */
  18.     static $pre = null;
  19.  
  20.     if ($pre === null) {
  21.         $precedence = array(
  22.             array('*', '/', '%'),
  23.             array('+', '-')
  24.         );
  25.  
  26.         $tmp = array();
  27.  
  28.         foreach ($precedence as $weight => $row) {
  29.             foreach ($row as $item) {
  30.                 $tmp[$item] = $weight;
  31.             }
  32.         }
  33.  
  34.         $pre = $tmp;
  35.     }
  36.  
  37.     return $pre;
  38. }
  39.  
  40. /**
  41.  * Splits the input into logical tokens
  42.  *
  43.  * e. g. "(3 + 4) * 2" => array("(", "3", "+", "4", ")", "*", "2")
  44.  *
  45.  * @param string $input
  46.  * @return array
  47.  */
  48. function tokenize($input)
  49. {
  50.     $temp = preg_split('/(\d+(?:\.\d+)?) | ([*\/%+,()-]) | ([a-z]+)/isx',
  51.             $input, null, PREG_SPLIT_NO_EMPTY | PREG_SPLIT_DELIM_CAPTURE);
  52.  
  53.     $tokens = array();
  54.  
  55.     foreach ($temp as $t) {
  56.         if (trim($t) !== '') {
  57.             $tokens[] = trim($t);
  58.         }
  59.     }
  60.  
  61.     return $tokens;
  62. }
  63.  
  64. /**
  65.  *
  66.  *
  67.  * @todo God function
  68.  *
  69.  * @staticvar array $funcs
  70.  * @param array $tokens
  71.  * @param array $precedences
  72.  * @return array
  73.  */
  74. function buildAst(array $tokens, array $precedences)
  75. {
  76.     /** @todo Supposed to be a cache. Code really needs OOP */
  77.     static $funcs = array(
  78.         '*' => 'mul', '/' => 'div', '%' => 'mod',
  79.         '+' => 'add', '-' => 'sub');
  80.  
  81.     // Single scalar value?
  82.  
  83.     if (count($tokens) === 1) {
  84.         return $tokens;
  85.     }
  86.  
  87.     // Functions? (e. g. sqrt, min, max, ...)
  88.  
  89.     $f = function ($a) {
  90.         $ret = false;
  91.         foreach ($a as $e) {
  92.             if (!is_array($e) && preg_match('/[a-z]+/i', $e) === 1) {
  93.                 $ret = true;
  94.                 break;
  95.             }
  96.         }
  97.         return $ret;
  98.     };
  99.  
  100.     while ($f($tokens)) {
  101.         $firstOpeningBracketIndex = -1;
  102.         $matchingClosingBracketIndex = -1;
  103.         $functionPos = -1;
  104.         $bracketCount = 0;
  105.  
  106.         foreach ($tokens as $index => $token) {
  107.             if ($functionPos === -1) {
  108.                 if (!is_array($token)
  109.                     && preg_match('/[a-z]+/i', $token) === 1
  110.                 ) {
  111.                     $functionPos = $index;
  112.                 }
  113.             } else {
  114.                 if ($token === '(') {
  115.                     if ($firstOpeningBracketIndex === -1) {
  116.                         $firstOpeningBracketIndex = $index;
  117.                     }
  118.  
  119.                     $bracketCount++;
  120.                 } else if ($token === ')') {
  121.                     $bracketCount--;
  122.  
  123.                     if ($bracketCount < 0) {
  124.                         throw new Exception('Too many closing brackets');
  125.                     }
  126.  
  127.                     if ($bracketCount === 0) {
  128.                         $matchingClosingBracketIndex = $index;
  129.                         break;
  130.                     }
  131.                 }
  132.             }
  133.         }
  134.  
  135.         if ($matchingClosingBracketIndex === -1) {
  136.             throw new Exception('Too many opening brackets');
  137.         }
  138.  
  139.         // construct Sub-AST
  140.  
  141.         $subTokenList = array_slice($tokens,
  142.                 $firstOpeningBracketIndex + 1,
  143.                 $matchingClosingBracketIndex - $firstOpeningBracketIndex - 1);
  144.  
  145.         $parts = array();
  146.         $partsTemp = array();
  147.         $brackCount = 0;
  148.  
  149.         // Generate a sub tree for each parameter (a, b in "f(a, b)")
  150.  
  151.         while (count($subTokenList) > 0) {
  152.             $first = array_shift($subTokenList);
  153.             if ($first === ',' && $brackCount === 0) {
  154.                 $parts[] = $partsTemp;
  155.                 $partsTemp = array();
  156.             } else {
  157.                 if ($first === '(') {
  158.                     $brackCount++;
  159.                 } else if ($first === ')') {
  160.                     $brackCount--;
  161.                 }
  162.                 $partsTemp[] = $first;
  163.             }
  164.         }
  165.  
  166.         $parts[] = $partsTemp;
  167.  
  168.         $subAst = array();
  169.         foreach ($parts as $part) {
  170.             $subAstTemp = buildAst($part, $precedences);
  171.  
  172.         /** @todo See corresponding todo item below */
  173.         if (count($subAstTemp) === 1) {
  174.             $subAstTemp = $subAstTemp[0];
  175.         }
  176.  
  177.             $subAst[] = $subAstTemp;
  178.         }
  179.  
  180.         array_unshift($subAst, $tokens[$functionPos]);
  181.  
  182.         array_splice($tokens,
  183.                 $firstOpeningBracketIndex - 1,
  184.                 $matchingClosingBracketIndex - $firstOpeningBracketIndex + 2,
  185.                 array($subAst));
  186.     }
  187.  
  188.  
  189.     // Brackets?
  190.  
  191.     while (in_array('(', $tokens)) {
  192.         $firstOpeningBracketIndex = -1;
  193.         $matchingClosingBracketIndex = -1;
  194.         $bracketCount = 0;
  195.  
  196.         foreach ($tokens as $index => $token) {
  197.             if ($token === '(') {
  198.                 if ($firstOpeningBracketIndex === -1) {
  199.                     $firstOpeningBracketIndex = $index;
  200.                 }
  201.  
  202.                 $bracketCount++;
  203.             } else if ($token === ')') {
  204.                 $bracketCount--;
  205.  
  206.                 if ($bracketCount < 0) {
  207.                     throw new Exception('Too many closing brackets');
  208.                 }
  209.  
  210.                 if ($bracketCount === 0) {
  211.                     $matchingClosingBracketIndex = $index;
  212.                     break;
  213.                 }
  214.             }
  215.         }
  216.  
  217.         if ($matchingClosingBracketIndex === -1) {
  218.             throw new Exception('Too many opening brackets');
  219.         }
  220.  
  221.         // construct Sub-AST
  222.  
  223.         $subAst = buildAst(
  224.             array_slice(
  225.                 $tokens,
  226.                 $firstOpeningBracketIndex + 1,
  227.                 $matchingClosingBracketIndex - $firstOpeningBracketIndex - 1
  228.             ), $precedences);
  229.  
  230.         /** @todo This is needed to fix an issue with single function calls in
  231.          * brackets "(min(1,2))"
  232.          */
  233.         if (count($subAst) === 1) {
  234.             $subAst = $subAst[0];
  235.         }
  236.  
  237.         array_splice($tokens,
  238.                 $firstOpeningBracketIndex,
  239.                 $matchingClosingBracketIndex - $firstOpeningBracketIndex + 1,
  240.                 array($subAst));
  241.     }
  242.  
  243.     // Finally, process operators (+, -, ...)
  244.  
  245.     do {
  246.         $n = -1;
  247.  
  248.         foreach ($tokens as $i => $item) {
  249.             if (!is_array($item) && !is_numeric($item)) {
  250.                 if ($n === -1
  251.                     || $precedences[$item] < $precedences[$tokens[$n]]
  252.                 ) {
  253.                     $n = $i;
  254.                 }
  255.             }
  256.         }
  257.  
  258.         if ($n > -1) {
  259.             /** @todo We could probably do something more clever than throwing
  260.              * exceptions
  261.              * (e. g. left padding "-" with "-1 *" and "+" with "0 +")
  262.              */
  263.             if ($n === 0) {
  264.                 throw new Exception('No left operand available before "'
  265.                         . $tokens[$n] . '"');
  266.             }
  267.  
  268.             if ($n === count($tokens) - 1) {
  269.                 throw new Exception('No right operand available after "'
  270.                         . $tokens[$n] . '"');
  271.             }
  272.  
  273.             // Function/operator name is always first entry
  274.             $repl = array($funcs[$tokens[$n]], $tokens[$n - 1],
  275.                           $tokens[$n + 1]);
  276.  
  277.             array_splice($tokens, $n - 1, 3, array($repl));
  278.         }
  279.     } while ($n > -1);
  280.  
  281.     return $tokens[0];
  282. }
  283.  
  284. /**
  285.  * Returns a debug string of the generated parse tree
  286.  *
  287.  * @param array $ast
  288.  * @return string
  289.  */
  290. function printAst(array $ast)
  291. {
  292.     $s = '';
  293.  
  294.     $cnt = count($ast);
  295.  
  296.     if ($cnt === 1) {
  297.         return $ast[0];
  298.     }
  299.  
  300.     $s .= $ast[0] . '(';
  301.  
  302.     for ($i = 1; $i < $cnt; $i++) {
  303.         $item = $ast[$i];
  304.         if (is_array($item)) {
  305.             $s .= printAst($item);
  306.         } else {
  307.             $s .= $item;
  308.         }
  309.         $s .= ', ';
  310.     }
  311.  
  312.     $s = rtrim(trim($s), ',') . ')';
  313.  
  314.     return $s;
  315. }
  316.  
  317. /**
  318.  *
  319.  * @param array $ast
  320.  * @return mixed The result of the input term
  321.  */
  322. function solveAst(array $ast)
  323. {
  324.     $s = '';
  325.  
  326.     $cnt = count($ast);
  327.  
  328.     if ($cnt === 1) {
  329.         return $ast[0];
  330.     }
  331.  
  332.     $op = $ast[0];
  333.  
  334.     $params = array();
  335.  
  336.     for ($i = 1; $i < $cnt; $i++) {
  337.         $item = $ast[$i];
  338.         if (is_array($item)) {
  339.             $params[] = solveAst($item);
  340.         } else {
  341.             $params[] = $item;
  342.         }
  343.     }
  344.  
  345.     $res = 0;
  346.  
  347.     /** @todo Superfluous parameters shouldn't be silently discarded */
  348.     switch (strtolower($op)) {
  349.         case 'mul':
  350.             $res = $params[0] * $params[1];
  351.             break;
  352.         case 'div':
  353.             $res = $params[0] / $params[1];
  354.             break;
  355.         case 'mod':
  356.             $res = $params[0] % $params[1];
  357.             break;
  358.         case 'add':
  359.             $res = $params[0] + $params[1];
  360.             break;
  361.         case 'sub':
  362.             $res = $params[0] - $params[1];
  363.             break;
  364.         case 'sqrt':
  365.             $res = sqrt($params[0]);
  366.             break;
  367.         case 'max':
  368.             $res = max($params);
  369.             break;
  370.         case 'min':
  371.             $res = min($params);
  372.             break;
  373.         default:
  374.             throw new Exception('Unknown operation: ' . $op);
  375.             break;
  376.     }
  377.  
  378.     return $res;
  379. }
  380.  
  381.  
  382. error_reporting(-1);
  383.  
  384.  
  385. $input = '(5 + 2) + ((7)) + (min(3, 2)) * (max(19, 32, 45 + 9, max(2, 3, 499.5)) + sqrt(45 - 9) * 7 / 2 + 21)';
  386.  
  387. #$input = '6 % (7 * (7 + 21) - 5) *19 + 45 - 2';
  388. #$input = '7';
  389.  
  390. $tokens = tokenize($input);
  391.  
  392. echo implode('  ', $tokens), "\n\n\n";
  393.  
  394. $precedences = getOperatorPrecedenceTable();
  395. $ast = buildAst($tokens, $precedences);
  396.  
  397. echo printAst($ast), "\n\n\n";
  398.  
  399. $result = solveAst($ast);
  400.  
  401. echo 'Result: ' . $result, "\n\n\n";
  402.  
  403. echo 'eval\'d result: ';
  404. eval('echo ' . $input . ';');
  405. echo "\n\n\n";
  406.  
  407.  
  408. echo "\n";
  409.  
  410.  
  411.  
  412.  
  413. // Example output:
  414.  
  415. /*
  416. (  5  +  2  )  +  (  (  7  )  )  +  (  min  (  3  ,  2  )  )  *  (  max  (  19
  417.  ,  32  ,  45  +  9  ,  max  (  2  ,  3  ,  499.5  )  )  +  sqrt  (  45  -  9  )
  418.  *  7  /  2  +  21  )
  419.  
  420.  
  421. add(add(add(5, 2), 7), mul(min(3, 2), add(add(max(19, 32, add(45, 9),
  422.     max(2, 3, 499.5)), div(mul(sqrt(sub(45, 9)), 7), 2)), 21)))
  423.  
  424.  
  425. Result: 1097
  426.  
  427.  
  428. eval'd result: 1097
  429. */
RAW Paste Data