Java Reference
In-Depth Information
messages is a program that checks whether symbols are balanced. In other
words, every { must correspond to a } , every [ to a ] , and so on. However,
simply counting the numbers of each symbol is insufficient. For example, the
sequence [()] is legal, but the sequence [(]) is wrong.
11.1.1 basic algorithm
A stack is useful here because we know that when a closing symbol such as )
is seen, it matches the most recently seen unclosed ( . Therefore, by placing an
opening symbol on a stack, we can easily determine whether a closing symbol
makes sense. Specifically, we have the following algorithm.
A stack can be
used to detect mis-
matched symbols.
1.
Make an empty stack.
2.
Read symbols until the end of the file.
a.
If the symbol is an opening symbol, push it onto the stack.
b.
If it is a closing symbol, do the following.
i. If the stack is empty, report an error.
ii. Otherwise, pop the stack. If the symbol popped is not the cor-
responding opening symbol, report an error.
3.
At the end of the file, if the stack is not empty, report an error.
In this algorithm, illustrated in Figure 11.1, the fourth, fifth, and sixth sym-
bols all generate errors. The } is an error because the symbol popped from the
top of the stack is a ( , so a mismatch is detected. The ) is an error because the
stack is empty, so there is no corresponding ( . The [ is an error detected when
the end of input is encountered and the stack is not empty.
figure 11.1
Stack operations
in a balanced-
symbol algorithm
Symbols: ( [ ] } ) [
[
(
(
(
[
eof*
(
[
]
}*
)*
[
Errors (indicated by *):
{ when expecting)
( with no matching opening symbol
[ unmatched at end of input
 
Search WWH ::




Custom Search