The rule to be used for a completely parenthesized infix expression is
1. Scan the infix expression from left to right.
2. When a "matched" pair of ''left" and "right" parentheses is encountered,
apply the operator to the operands enclosed within the pair of parentheses, and replace the paired parentheses and the contained operator and operands by the result. Continue scanning from this point.
One problem remains: How do we evaluate infix expressions that are not completely parenthesized? Recall that there are standard rules for interpreting infix expressions in this case. These rules are also incorporated in high-level languages. They are necessary because parentheses are not always available to signal what is to be done next. For example, if we evaluate
then when the * is encountered, the stacks appear as
The operator * signals that, had the expressions been completely parenthesized, a left parenthesis would have occurred just before the b, or else a right parenthesis would have occurred just after the b. In other words, the appearance of the operator requires a decision as to whether b should be considered an operand of *or an operand of +. The standard rules resolve such ambiguities by assigning priorities or precedence values to operators, assuming a left-to-right scan of the expression. For the binary operators, +, -, *, /, and ** (for exponentiation), the priorities are as follows:
1. Exponentiation (**) has the highest priority.
2. Multiplication and division (*, /) have the same priority, which is higher than that of addition or subtraction (+, -).
3. Addition and subtraction (+, -) have the same priority.
A left parenthesis also needs a priority, the lowest.
Whether b is an operand of * or + can then be resolved by taking b as an operand of the highest priority operator (* in this case). Again, parentheses may be used to override priorities. For example, in
b is to be associated with the + operator.
Example 4.6
In order to see how any infix expression is evaluated using priorities, and to develop an algorithm for this evaluation, consider the expression,
To evaluate it, when the first * is encountered the situation will be
In this case, since the left parenthesis is on top of the operator stack, the * should be placed on top of the operator stack, and scanning continued. After c, division(/) is encountered and the stacks become
At this point a decision must be made with respect to c: either it is to be associated with * (at the top of the stack) or with / (the current operator being processed). The standard rules associate c with the operator of highest priority. In this case, since * and / have equal priorities, associate c with the leftmost of the two operators in the input?/FONT>that is, the top stack operator. Thus, the * must be popped, c and b must be popped, the * must be applied to b and c, and the result, (b * c), placed on top of the operand stack. Then the / must be placed on the operator stack. Had the current operator been of higher priority (say, **), then the current operator should simply be placed on the operator stack.
In the example, after / and d are processed, the stacks are as follows:
The ** becomes the current operator, and d must be associated with it or with /. Since ** has higher priority, place it on the operator stack; the result after processing e is
The current input character being scanned is now a right parenthesis. This "matches" the topmost left parenthesis on the stack. The next steps are to pop the operator stack; pop the operand stack to obtain the top two operands; apply **to them, and place the result back on the top of the operand stack. Then pop the operator stack; pop the operand stack to obtain the top two operands; apply / to them and place the result back on top of the operand stack; pop the stack again; and notice that a left parenthesis has appeared, signaling completion of the process for the current input character. The result is
Finally, the last * is processed. It has higher priority than +, so it is placed on the operator stack. f is then processed and placed on the operand stack, yielding
Since the input is exhausted, the final steps are, for each remaining operator on the operator stack, to pop the operator stack, remove the required number of top operands from the operand stack, apply the operator, and place the result back on top of the operand stack. The final result appears at the top of the operand stack.a + b * c/d
Operand Stack Operator Stack
--------------------------------
b +
a
(a + b) * c/d
a + (b * c/d ** e) *f n
Operand Stack Operator Stack
--------------------------------
b (
a +
Operand Stack Operator Stack
---------------------------------
c *
b (
a +
Operand Stack Operator Stack
---------------------------------
d /
(b * c) (
a +
Operand Stack Operator Stack
---------------------------------
e **
d /
(b * c) (
a +
Operand Stack Operator Stack
----------------------------------
((b * c)/(d ** e)) +
a
Operand Stack Operator Stack
-----------------------------------
f *
((b * c)/(d ** e)) +
a