518
Graphs and Trees
2 Named for the Polish logician J. Lukasiewicz, who first used it.
example 28
Example 23 showed how algebraic expressions can be represented as binary trees.
If we do an inorder traversal of the expression tree, we retrieve the original algebraic expression. For the expression tree of Figure 6.48, for example, an inorder
traversal gives the expression
(2 + x) * 4
where the parentheses are added as we complete the processing of a subtree. This
form of an algebraic expression, where the operation symbol appears between the
two operands, is called infix notation. Parentheses are necessary here to indicate the
order of operations. Without parentheses, the expression becomes 2 + x * 4, which
is also an infix expression but, because of the order of precedence of multiplication
over addition, is not what is intended.
2
x
4
+
*
Figure 6.48
A preorder traversal of Figure 6.48 gives the expression
* + 2 x 4
Here the operation symbol precedes its operands. This form of an expression is
called prefix notation, or polish notation.
2
The expression can be translated into
infix form as follows:
* + 2 x 4 S * (2 + x) 4 S (2 + x) * 4
A postorder traversal gives the expression
2 x + 4 *
where the operation symbol follows its operands. This form of an expression is
called postfix notation, or reverse polish notation (or just rpn). The expression
can be translated into infix form as follows:
2 x + 4 * S (2 + x) 4 * S (2 + x) * 4
Neither prefix nor postfix form requires parentheses to avoid ambiguity. These
notations therefore provide more efficient, if less familiar, representations of algebraic expressions than infix notation. Such forms can be evaluated sequentially,
with no need for “look-ahead” to locate parenthesized expressions. Compilers
often change algebraic expressions in computer programs from infix to postfix
notation for more efficient processing.
Graphs and Trees
2 Named for the Polish logician J. Lukasiewicz, who first used it.
example 28
Example 23 showed how algebraic expressions can be represented as binary trees.
If we do an inorder traversal of the expression tree, we retrieve the original algebraic expression. For the expression tree of Figure 6.48, for example, an inorder
traversal gives the expression
(2 + x) * 4
where the parentheses are added as we complete the processing of a subtree. This
form of an algebraic expression, where the operation symbol appears between the
two operands, is called infix notation. Parentheses are necessary here to indicate the
order of operations. Without parentheses, the expression becomes 2 + x * 4, which
is also an infix expression but, because of the order of precedence of multiplication
over addition, is not what is intended.
2
x
4
+
*
Figure 6.48
A preorder traversal of Figure 6.48 gives the expression
* + 2 x 4
Here the operation symbol precedes its operands. This form of an expression is
called prefix notation, or polish notation.
2
The expression can be translated into
infix form as follows:
* + 2 x 4 S * (2 + x) 4 S (2 + x) * 4
A postorder traversal gives the expression
2 x + 4 *
where the operation symbol follows its operands. This form of an expression is
called postfix notation, or reverse polish notation (or just rpn). The expression
can be translated into infix form as follows:
2 x + 4 * S (2 + x) 4 * S (2 + x) * 4
Neither prefix nor postfix form requires parentheses to avoid ambiguity. These
notations therefore provide more efficient, if less familiar, representations of algebraic expressions than infix notation. Such forms can be evaluated sequentially,
with no need for “look-ahead” to locate parenthesized expressions. Compilers
often change algebraic expressions in computer programs from infix to postfix
notation for more efficient processing.