Finally, execution

The actual code to execute part of a stack needs to be its own function, as we will be calling it recursively to handle complex expressions. What this needs to do is pop off the last element in the stack (an operator - this is Reverse Polish Notation after all), then try to pop off the right-hand operand. I say "try to" because this is where the recursion comes in: if there is a complex expression, either the right-hand operator or the left-hand operator will be another operator, in which case we need to re-call execute(), passing in the same stack.

If we have both left and right operands, we're ready to execute the instruction. The action performed in the instruction is entirely dependent on the token of the operator - are we printing a value out? Multiplying a value?

If we are performing a calculation, i.e. FOO_PLUS or FOO_MULTIPLY, we need to perform the calculation and return the result in a new token. Otherwise, we need to act directly by either assigning the variable or printing it out.

One last thing before you read the code: while it's possible to have detailed checks everywhere to see whether an operand is a string or a variable, it's much easier to have just one function that does all the hard work and use that wherever a variable's value is wanted. In the example below, I've used the function getval() for this purpose:

function execute(&$stack) {
    GLOBAL $variables;
    $operator = array_pop($stack);

    if ($stack[count($stack) - 1]->type == IS_OPERATOR) {
        $right = execute($stack);
    } else {
        $right = array_pop($stack);
    }

    if (count($stack)) {
        if ($stack[count($stack) - 1]->type == IS_OPERATOR) {
            $left = execute($stack);
         else {
            $left = array_pop($stack);
        }
    }

    switch($operator->token) {
        case FOO_ASSIGNEQUALS:
            $variables[$left->val] = getval($right);
            break;
        case FOO_PLUS:
            return new token(IS_OPERAND, FOO_NUMBER, getval($left) + getval($right));
        case FOO_MULTIPLY:
            return new token(IS_OPERAND, FOO_NUMBER, getval($left) * getval($right));
        case FOO_PRINT:
            print getval($right);
            print "\n";
    }
}

Here's the accompanying code for getval():

function getval($token) {
    GLOBAL $variables;

    if ($token->token == FOO_VARIABLE) {
        return $variables[$token->val];
    } else {
        return $token->val;
    }
}

I'll explain the function recursion in a little more depth momentarily, but first I'd like to discuss the rest of the code. The switch($operator->token) line is where it decides what action to take based upon the operator, so if the operator was FOO_ASSIGNEQUALS it performs an assign. The $variables array is designed to have variable names as its keys and variables values as its values, which is why it's $variables[$left->val]. The call to getval() is there so that if we say "a = b", a won't be set to "b". Instead, the value of b will be looked up and assigned to a, thanks to getval(). Printing is almost exactly the same - retrieve the value of the token, and print it out.

Both FOO_PLUS and FOO_MULTIPLY work in the same way - they both take the values of their operands (using getval() again), run it through an add or a multiply respectively, then return the value inside a new token. This is where the recursiveness comes in.

If we find either left or right operand of an operator is another operator, there is more work to be done. This is because operands to the left of our stack are of higher priority than those to the right. Thus:

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

That will give us a stack like this:

a b c + * print

Starting off, "print" will look to its right operand to find *, an operator. It leaves the * on the stack, but recursively calls execute() again, passing in the stack.

This time the stack looks like this:

a b c + *

The operator, *, is taken off the stack, and looks to its right operand to find "+", an operator. It leaves the + on the stack, but recursively calls execute() again, passing in the stack.

Now the stack looks like this:

a b c +

The operator, +, is taken off the stack, and looks to its right operand to find "c", which it pops off, and looks to its left operand to find "b", which it also pops off. We now have a complete operation, so we perform b + c. Now, the result of this is returned back inside a new token. Why? Because if you look at the code, the recursive execute() call looks like this:

$right = execute($stack);

That is, "call execute(), and use as your other operator whatever it returns". So, once we add b and c, we return the result (we'll call it d), which gets used as the right-hand operator for the * operator. If we were to replace the b c addition with its result, it would look like this:

a d *

As you can see, the right-hand operand is now ready for use, meaning that a can be multiplied by d. This itself returns a new token back to its caller, which was the operator print. This time we just take the right-hand operand (print does not have a left-hand operand), and print it out.

Hopefully that all made sense - if not, I suggest you get a decent PHP debugger and step through the code line by line to get a full understanding.

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