Given an infix expression that is completely parenthesized, such as
((a + b) * (c/d))
you know how to evaluate it. This is because you have grown accustomed to the rules for its evaluation, although you might be hard pressed to state those rules completely and precisely. In any case, parentheses signal how the operators are to be applied to the operands, indicating that (a + b) and (c/d) must be evaluated first before applying the * operator. Removing all parentheses yields
a + b * c/d
Unless conventions or rules are given, this expression is ambiguous. Its five distinct interpretations correspond to the ways in which parentheses may be placed:
((a + b) * (c/d))
(((a + b) * c)/d)
((a + (b * c))/d)
(a + ((b * c)/d))
(a + (b * (c/d)))
A postfix expression such as
ab + cd/*
makes little sense, for you are not used to it, having little experience in interpreting or evaluating it. The rule to be used is as follows:
1. Scan the postfix expression from left to right.
2. Whenever an operator is encountered,
replace it, and the immediately preceding number of operands required by that operator, with the result of applying that operator to those operands.
3. Treat this replacement as an operand, and continue scanning from this point.
Thus the postfix expression is equivalent to the infix expression
((a + b) * (c/d))
The rule, in generating this expression, produces the two intermediate expressions: (a + b)cd/*, (a + b)(c/d)*.
The following list shows the five fully parenthesized infix expressions representing the interpretations of a + b * c/d and their corresponding postfix expressions.
((a + b) * (c/d)) .... ab + cd/*
(((a + b) * c)/d) .... ab + c * d/
((a + (b * c))/d) .... abc* + d/
(a + ((b * c)/d)) .... abc*d/+
(a + (b * (c/d))) .... abcd/*+
These examples emphasize two points:
1. The rule for evaluating postfix expressions allows no ambiguity. It determines precisely the meaning or interpretation of the postfix expression.
2. An infix expression, unless fully parenthesized, may be ambiguous in its meaning or interpretation.
It is because of statement 1 that postfix notation, or postfix expressions, are called parentheses-free. A similar rule allows prefix notation, or prefix expression, to be parentheses-free .
Furthermore, evaluation of a postfix expression is easily accomplished by scanning the expression from left to right and using a stack to retain operands and
Input Operand Stack
a a
b b
a
c c
b
a
* (b * c)
a
d d
(b * c)
a
/ ((b * c)/d)
a
+ (a + ((b * c)/d)
results of intermediate evaluations. Any operand that is encountered is placed on an operand stack. When an operator is encountered, its operands are taken from the top of the stack, the operator is applied, and the result is put on the top of the stack. The process is illustrated in the following example.
Example 4.5
Table 4.2 shows the contents of the operand stack after each input is processed, simulating the procedure for evaluation of a postfix expression. The expression is ABC*D/+. n
Since the procedure for the evaluation of an arithmetic expression using a stack is relatively straightforward and requires no parentheses, why don't programmers write arithmetic expressions in postfix notation only? It is because they are so used to infix notation that they don't want to change. As a result, high-level languages accept infix expressions rather than postfix. This leads back to the question of how infix expressions may be evaluated.