Binary Expression Evaluation

Three ways to write and evaluate binary expressions

There are three common forms in that one may use to write and evaluate binary arithmetic (or other binary) expressions, including

• infix form, in which an operator comes between its two operands (which, of course, is the "usual form" that we use to write most of our arithmetic expressions on a daily basis) [In this context, it is extremely important to understand fully the idea of "operator precedence" and also to be able to "fully parenthesize" an arithmetic expression so that there is no ambiguity about any of the operations required to evaluate it.]
• prefix form, in which an operator comes before its two operands
• postfix form, in which an operator comes after its two operands

Here are some examples of each:

Let's look at how we evaluate expressions in each of these forms.

Evaluating Infix Expressions and Binary Expression Trees

First, we know, or we should know, how to evaluate expressions in infix form, since this is the form we use in our everyday lives (if our everyday lives involve expression evaluation).

But what if the expression is not in our "usual form" but in a binary expression tree instead?

The first thing to note in this context is that the value of the expression is completely determined by the structure of the tree. That is, given the binary expression tree, we can evaluate the expression it contains without having to worry about any precedence rules, or where parentheses might have been located when the expression was written in the usual infix form that we use for such expressions.

So, suppose a valid binary expression, as defined above, has been loaded into its corresponding valid binary expression tree, using the routine whose pseudocode is given above. Then the recursive definition of such a tree also provides us with a convenient recursive algorithm for the evaluation of the expression contained in the tree. The "value" of any "node" in the tree is interpreted to be

• The value of the integer in the node, if the node does contain an integer.
• Otherwise, it is the value of the node which is the left child of the given node, combined with the value of the node which is the right child of the given node (in that order) using the operator that is in the given node.

This interpretation gives us this pseudocode for the evaluation routine, valueOf, say,

Algorithm valueOf(someNode)
if someNode contains an integer
    return the value of that integer
else
    return valueOf(someNode's left Child) op valueOf(someNode's right child)
endif

from which it follows that the value of the complete binary expression contained in a binary expression tree will be valueOf(root), where "root" is the root node of that tree.

Evalualting Prefix Expressions

Here is the pseudocode for a simple recursive algorithm which evaluates an expression in prefix form:

Algorithm valueOfPrefixExpression(prefixExpression)
-------------------------------------------------
Input: a valid positive-integer arithmetic expression in prefix form
Return value: the value of the prefix expression
--------------------------------------------------------------------
if next token is an integer
    return the integer
else
    Read an operator, say op
    firstOperand gets valueOfPrefixExpression(remainingExpression)
    secondOperand gets valueOfPrefixExpression(remainingExpression)
    return firstOperand op secondOperand
endif

Evaluating Postfix Expressions

Finally, here is the pseudocode for a simple algorithm which reads and finds the value of an expression in postfix form. It makes use of an "auxiliary stack".

Algorithm ReadAndReturnValueOf(postfixExpression)
-------------------------------------------------
Input: a valid positive-integer arithmetic expression in postfix form
Return value: the value of the postfix expression
---------------------------------------------------------------------
while more tokens (operands or operators) to read
    Read next token
    if token is an operand
        Push token onto stack
    else if token is an operator ("op", say)
        Pop stack and put value in temp2
        Pop stack and put value in temp1
        Push the value of temp1 op temp2 back onto stack
    endif
endwhile
Pop value from stack and return it

It is very useful and informative to draw a picture of this process, with time proceeding from left to right and a picture of the stack and its contents after each token has been read and processed. If a question like this is asked on a test or exam, you will be expected to show a pictorial record of the evaluation procedure in the same manner demonstrated in class. See here for an example of such a diagram.

Important Note

The prefix and postfix forms of any expression may be evaluated unambiguously, unlike the infix form, which needs (or at least, may need) additional input in the form of a precedence table, and/or one or more pairs of parentheses, to be properly evaluated.

Relationships between binary expression trees and the prefix, postfix and infix forms

The relationship between the binary expression tree form of a binary expression and these other forms may be summarized as follows:

• Performing an inorder traversal of a binary expression tree and recording the node contents produces the "infix form" of the expression stored in the tree.
• Performing a preorder traversal of a binary expression tree and recording the node contents produces the "prefix form" of the expression stored in the tree.
• Performing a postorder traversal of a binary expression tree and recording the node contents produces the "postfix form" of the expression stored in the tree.