Operator precedence

This might sound like quite a hard thing to implement, but in actuality it's not. But first, we need to identify the problem - try saving this text as script.foo:

a = 45;
b = 2;
c = 10;
print a * b + c;

Now, that will be converted to the following RPN:

a b c + *

As we've seen, that currently results in b being added to c, then the result being multiplied by a. Most kids at school learn an acronym similar to BODMAS, which stands for "Brackets out, Division, Multiplication, Addition, Subtraction", and refers to the order in which an expression is evaluated. That is, division should be done before multiplication, and multiplication should be done before addition.

Currently we are evaluating the equation like this:

a * (b + c)

Given the values above, that would 540, which is incorrect. Multiplication is of a higher precedence than addition, so it should be evaluated like this:

(a * b) + c

That should output 100 - 45 multiplied by 2, then added to 10. In order to alter the way our expression is evaluated, we need to generate the correct RPN. So, instead of our previous "a b c + *", what we actually need is "a b * c +". Happily enough, making this change is actually rather easy, because there is a simple algorithm to generate precedence-respecting RPN, which is this:

1. Get new operator

2. Check against all the last operator in the operator array

3. If the last operator is of higher precedence, pop it off and push it onto the result stack

4. Go to step 2

5. Once there are no more operators in the operator array or the last one in there is of a lower precedence, push the new operator onto the end

This entire algorithm can be implemented in our main() function with this code:

if ($token != FOO_SEMICOLON) {
    while (count($operators) && $precedence[$operators[count($operators) - 1]->token] > $precedence[$token]) {
        $higher_op = array_pop($operators);
        array_push($stack, $higher_op);
    }
    $operators[] = new token(IS_OPERATOR, $token, NULL);
}

Put those new lines in place of these old ones:

if ($token != FOO_SEMICOLON) {
    $operators[] = new token(IS_OPERATOR, $token, NULL);
}

Yes, the new version is longer, but it's because it has to into a while loop through the current operators list to make sure there are no operators on there that are of a higher precedence. We'll be looking at the $precedence array momentarily, but first take a good look at what the new loop does:

// while there are still operators in the array while (count($operators)
// and the precedence of the last operator in the array...
&& $precedence[$operators[count($operators) - 1]->token]

// ...is greater than the precedence of the next token
> $precedence[$token])

As you can see, it is an exact representation of what we wanted. The content of the loop pops off the last operator and adds it to the result array.

Handling the precedence needs to be done using an array, with each operator token having a key, and the values in the array being equal to the precedence of each operator. As you can see, our loop compares operators by their $precedence value, with lower values being considered to mean a lower-priority token.

So, our $precedence array needs to look like this:

$precedence = array (FOO_PRINT => 0, FOO_ASSIGNEQUALS => 1, FOO_PLUS => 2, FOO_MULTIPLY => 3);

You can assign any values you want - 0, 10, 20, and 30, or 0, 100, 200, and 300 - as long as the order remains as shown there. The order there puts multiply as the highest-precedence operator, followed by plus, equals, and finally print. This fits with the BODMAS acronym nicely, although if you add more of your own symbols you'll need to figure out the precedence yourself. The above list is in-line with the precedence PHP uses itself, so you might find it best just to mimic the same precedence in your own language, as PHP uses the same list as various other languages. You might want to skip backwards to the chapter on variables and operators for the list of PHP's operators and their precedences.

If you try running the same script as before, you should get the correct answer (100), as the system only required those two changes to work.

Copyright ©2015 Paul Hudson. Follow me: @twostraws.