One intuitive way to process arithmetic expressions with a
computer is using an *expression tree*. An
expression tree is a binary tree consisting of nodes containing two
types of objects: *operators* and *terminal
values* . Operators are objects that have operands; terminal
values are objects that have no operands.

The idea behind an expression tree is simple: the subtrees
rooted at the children of each node are the operands of the operator
stored in the parent (see Figure
9.5). Operands may be terminal values, or they may be other
expressions themselves. Expressions are expanded in subtrees; terminal
values reside in leaf nodes. One of the nice things about this idea is
how easily an expression tree allows us to translate an expression
into one of three common representations: *prefix*,
*infix*, and *postfix*. To
obtain these representations, we simply traverse the tree using a
preorder, inorder, or postorder traversal.

Traversing the tree in Figure 9.5 in preorder, for example, yields the prefix expression × / - 74 10 32 + 23 17. To evaluate a prefix expression, we apply each operator to the two operands that immediately follow it. Thus, the prefix expression just given is evaluated as:

( x ( / ( - 74 10 ) 32 ) ( + 23 17 ) ) = 80

Infix expressions are the expressions we are most familiar with from mathematics, but they are not well suited to processing by a computer. If we traverse the tree of Figure 9.5 using an inorder traversal, we get the infix ...

Start Free Trial

No credit card required