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

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;
}