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

1 /**
2 * Process an operator by taking two items off the postfix
3 * stack, applying the operator, and pushing the result.
4 * Print error if missing closing parenthesis or division by 0.
5 */
6 private void binaryOp( int topOp )
7 {
8 if( topOp == OPAREN )
9 {
10 System.err.println( "Unbalanced parentheses" );
11 opStack.pop( );
12 return;
13 }
14 long rhs = postfixPop( );
15 long lhs = postfixPop( );
16
17 if( topOp == EXP )
18 postfixStack.push( pow( lhs, rhs ) );
19 else if( topOp == PLUS )
20 postfixStack.push( lhs + rhs );
21 else if( topOp == MINUS )
22 postfixStack.push( lhs - rhs );
23 else if( topOp == MULT )
24 postfixStack.push( lhs * rhs );
25 else if( topOp == DIV )
26 if( rhs != 0 )
27 postfixStack.push( lhs / rhs );
28 else
29 {
30 System.err.println( "Division by zero" );
31 postfixStack.push( lhs );
32 }
33 opStack.pop( );
34 }

figure 11.19
The BinaryOp routine
for applying topOp to
the postfix stack

We want to assign a number to each level of precedence. The higher the
number, the higher is the precedence. We could assign the additive operators
precedence 1, multiplicative operators precedence 3, exponentiation prece-
dence 5, and parentheses precedence 99. However, we also need to take into
account associativity. To do so, we assign each operator a number that repre-
sents its precedence when it is an input symbol and a second number that
represents its precedence when it is on the operator stack. A left-associative
operator has the operator stack precedence set at 1 higher than the input sym-
bol precedence, and a right-associative operator goes the other way. Thus the
precedence of the + operator on the stack is 2.