Stacks and compilers - Data Structures and Problem Solving Using Java - page 454

1 /**
2 * Print an error message if clSym does not match opSym.
3 * Update errors.
4 */
5 private void checkMatch( Symbol opSym, Symbol clSym )
6 {
7 if( opSym.token == '(' && clSym.token != ')' ||
8 opSym.token == '[' && clSym.token != ']' ||
9 opSym.token == '{' && clSym.token != '}' )
10 {
11 System.out.println( "Found " + clSym.token + " on line " +
12 tok.getLineNumber( ) + "; does not match " + opSym.token
13 + " at line " + opSym.theLine );
14 errors++;
15 }
16 }

figure 11.9
The checkMatch routine for checking that the closing symbol matches the opening symbol

a simple calculator

11.2

Some of the techniques used to implement compilers can be used on a smaller
scale in the implementation of a typical pocket calculator. Typically, calcula-
tors evaluate infix expressions, such as 1+2 , which consist of a binary operator
with arguments to its left and right. This format, although often fairly easy to
evaluate, can be more complex. Consider the expression

1 + 2 * 3

Mathematically, this expression evaluates to 7 because the multiplication
operator has higher precedence than addition. Some calculators give the
answer 9 , illustrating that a simple left-to-right evaluation is not sufficient; we
cannot begin by evaluating 1+2 . Now consider the expressions

In an infix expres-
sion a binary opera-
tor has arguments
to its left and right.

10 - 4 - 3
2 ^ 3 ^ 3

in which ^ is the exponentiation operator. Which subtraction and which exponen-
tiation get evaluated first? On the one hand, subtractions are processed left-to-
right, giving the result 3 . On the other hand, exponentiation is generally processed
right-to-left, thereby reflecting the mathematical rather than . Thus sub-
traction associates left-to-right, whereas exponentiation associates from right-to-
left. All of these possibilities suggest that evaluating an expression such as

When there are
several operators,
precedence and
associativity deter-
mine how the oper-
ators are
processed.

2 3 3 () 2 3

3