The collections api - Data Structures and Problem Solving Using Java - page 260

A stack is useful for checking unbalanced symbols because we know that
when a closing symbol such as ) is seen, it matches the most recently seen
unclosed ( . Therefore, by placing opening symbols on a stack, we can easily check
that a closing symbol makes sense. Specifically, we have the following algorithm.

A stack can be
used to check for
unbalanced
symbols.

1. Make an empty stack.

2. Read symbols until the end of the file.

a. If the token is an opening symbol, push it onto the stack.

b. If it is a closing symbol and if the stack is empty, report an error.

c. Otherwise, pop the stack. If the symbol popped is not the corre-

sponding opening symbol, report an error.

3. At the end of the file, if the stack is not empty, report an error.

In Section 11.1 we will develop this algorithm to work for (almost) all
Java programs. Details include error reporting, and processing of comments,
strings, and character constants, as well as escape sequences.

The algorithm to check balanced symbols suggests a way to implement
method calls. The problem is that, when a call is made to a new method, all the
variables local to the calling method need to be saved by the system; otherwise,
the new method would overwrite the calling routine's variables. Furthermore,
the current location in the calling routine must be saved so that the new method
knows where to go after it is done. The reason that this problem is similar to bal-
ancing symbols is because a method call and a method return are essentially the
same as an open parenthesis and a closed parenthesis, so the same ideas should
apply. This indeed is the case: As discussed in Section 7.3, the stack is used to
implement method calls in most programming languages.

The stack is used
to implement
method calls in
most program-
ming languages.

A final important application of the stack is the evaluation of expressions in
computer languages. In the expression 1+2*3 , we see that at the point that the * is
encountered, we have already read the operator + and the operands 1 and 2 . Does
* operate on 2 , or 1+2 ? Precedence rules tell us that * operates on 2 , which is the
most recently seen operand. After the 3 is seen, we can evaluate 2*3 as 6 and then
apply the + operator. This process suggests that operands and intermediate results
should be saved on a stack. It also suggests that the operators be saved on the stack
(since the + is held until the higher precedence * is evaluated). An algorithm that
uses this strategy is operator precedence parsing , and is described in Section 11.2.

The operator prece-
dence parsing
algorithm uses a
stack to evaluate
expressions.

6.6.3 queues

Another simple data structure is the queue , which restricts access to the least
recently inserted item. In many cases being able to find and/or remove the
most-recently inserted item is important. But in an equal number of cases, it is
not only unimportant, it is actually the wrong thing to do. In a multiprocessing

The queue
restricts access to
the least recently
inserted item.