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

on the internet

Both application programs are available. You should probably download the
balancing program; it may help you debug other Java programs.

Balance.java Contains the balanced symbol program.

Tokenizer.java Contains the Tokenizer class implementation for check-

ing Java programs.

Evaluator.java Contains the expression evaluator.

exercises

IN SHORT
11.1

Show the result of running the balanced symbol program on
a. }
b. ( }
c. [ [ [
d. ) (
e. [ ) ]

Show the postfix expression for
a. 1 + 2 - 3 ^ 4
b. 1 ^ 2 - 3 * 4
c. 1 + 2 * 3 - 4 ^ 5 + 6
d. ( 1 + 2 ) * 3 - ( 4 ^ ( 5 - 6 ) )

11.2

For the infix expression a + b ^ c * d ^ e ^ f - g - h / ( i + j ) ,
do the following:
a.

11.3

Show how the operator precedence parsing algorithm generates
the corresponding postfix expression.

b. Show how a postfix machine evaluates the resulting postfix

expression.

c. Draw the resulting expression tree.

IN THEORY
11.4

For the balanced symbol program, explain how to print out an error
message that is likely to reflect the probable cause.

In general terms, explain how unary operators are incorporated into
expression evaluators. Assume that the unary operators precede their
operands and have high precedence. Include a description of how
they are recognized by the state machine.

11.5