Find answer to string equation without using eval()

Question

I need a way of taking an equation given as a string and finding it's mathematical answer, the big caveat is that I can't use eval().

I know the equation will only ever contain numbers, the four mathematical operators (i.e. * / + -) and parentheses, it may or may not have spaces in the string. Here's a couple of examples.

4 * 4
4+6/3
(3 / 2)*(4+8)
(4+8) * 2

I'm guessing that it's going to have to be done with some kind of regex?

Answer 1

Math expressions aren't regular. They're context-free.

Your best bet is to parse them using well-known math parsing algorithms like the shunting yard algorithm. All you have to worry about is implementing the algorithm in PHP. You might even be able to find PHP implementations of it online.

Answer 2

Evaluating string formulas is rather easy when they are as simple as this. See half a dozen answers at http://stackoverflow.com/questions/1384811/code-golf-mathematical-expression-evaluator-full-pemdas

Answer 3

Just in case anybody's interested here is the algorithm I came up with in PHP for producing Reverse Polish Notation

function convertToRPN($equation)

{
    $equation = str_replace(' ', '', $equation);
    $tokens = token_get_all('<?php ' . $equation);
    $operators = array('*' => 1, '/' => 1, '+' => 2, '-' => 2);
    $rpn = '';
    $stack = array();
    $size = count($tokens);             
    for($i = 1; $i < $size; $i++) {
     if(is_array($tokens[$i])) {
      $rpn .= $tokens[$i][1] . ' ';
     } else {
      if(empty($stack) || $tokens[$i] == '(') {
       $stack[] = $tokens[$i];
      } else {
       if($tokens[$i] == ')') {
        while(end($stack) != '(') {
         $rpn .= array_pop($stack);
        }
        array_pop($stack);
       } else {
        while(!empty($stack) && end($stack) != '(' && $operators[$tokens[$i]] >= $operators[end($stack)]) {
         $rpn .= array_pop($stack);
        }
        $stack[] = $tokens[$i];
       }
      }
     }
    }

    while(!empty($stack)) {
     $rpn .= array_pop($stack);
    }

    return $rpn;
}