Java Reference
In-Depth Information
figure 11.12
Examples of using
associativity to break
ties in precedence
Infix
Expression
Postfix
Expression
Associativity
Left-associative: Input
+
is lower than stack
+
.
2 + 3 + 4
2 3 + 4 +
Right-associative: Input
^
is higher than stack
^
.
2
^
3
^
4
2 3 4
^^
when it is on the stack. Consequently, the input left parenthesis is simply
placed on the stack. When a right parenthesis appears on the input, we pop the
operator stack until we come to a left parenthesis. The operators are written,
but the parentheses are not.
The following is a summary of the various cases in the operator prece-
dence parsing algorithm. With the exception of parentheses, everything
popped from the stack is output.
Operands:
Immediately output.
n
Close parenthesis:
Pop stack symbols until an open parenthesis
appears.
n
Operators:
Pop all stack symbols until a symbol of lower precedence
or a right-associative symbol of equal precedence appears. Then push
the operator.
n
End of input:
Pop all remaining stack symbols.
n
As an example, Figure 11.13 shows how the algorithm processes
1 - 2
^
3
^
3 - ( 4 + 5 * 6 ) * 7
Below each stack is the symbol read. To the right of each stack, in boldface, is
any output.
11.2.3
implementation
We now have the theoretical background required to implement a simple cal-
culator. Our calculator supports addition, subtraction, multiplication, division,
and exponentiation. We write an
Evaluator
class that works on
long
integers.
We make a simplifying assumption: Negative numbers are not allowed. Dis-
tinguishing between the binary minus operator and the unary minus requires
extra work in the scanning routine and also complicates matters because it
introduces a nonbinary operator. Incorporating unary operators is not difficult,
but the extra code does not illustrate any unique concepts and thus we leave it
for you to do as an exercise.
The
Evaluator
class
will parse and eval-
uate infix expres-
sions.
Search WWH ::
Custom Search