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

the stack for use as a sentinel (which is done in the constructor). If we treat it
as a right-associative operator, it is covered under the operator case.
The remaining method is processToken , which is shown in Figure 11.21.
When we see an operand, we push it onto the postfix stack. When we see a
closing parenthesis, we repeatedly pop and process the top operator on the
operator stack until the opening parenthesis appears (lines 18-19). The open-
ing parenthesis is then popped at line 21. (The test at line 20 is used to avoid
popping the sentinel in the event of a missing opening parenthesis.) Otherwise,
1 /**
2 * After a token is read, use operator precedence parsing
3 * algorithm to process it; missing opening parentheses
4 * are detected here.
5 */
6 private void processToken( Token lastToken )
7 {
8 int topOp;
9 int lastType = lastToken.getType( );
10
11 switch( lastType )
12 {
13 case VALUE:
14 postfixStack.push( lastToken.getValue( ) );
15 return;
16
17 case CPAREN:
18 while( ( topOp = opStack.peek( ) ) != OPAREN && topOp != EOL )
19 binaryOp( topOp );
20 if( topOp == OPAREN )
21 opStack.pop( ); // Get rid of opening parenthesis
22 else
23 System.err.println( "Missing open parenthesis" );
24 break;
25
26 default: // General operator case
27 while( precTable[ lastType ].inputSymbol <=
28 precTable[ topOp = opStack.peek( ) ].topOfStack )
29 binaryOp( topOp );
30 if( lastType != EOL )
31 opStack.push( lastType );
32 break;
33 }
34 }
figure 11.21
The processToken routine for processing lastToken , using the operator precedence parsing algorithm