Java Reference
In-Depth Information
After pushing the first three open delimiters onto the stack, the open parenthesis is at the top of
the stack. The next delimiter, the close parenthesis, pairs with the open parenthesis at the top of the
stack. We pop the stack and continue by comparing the close bracket with the delimiter now at the
top of the stack. They correspond, so we pop the stack again and continue by comparing the close
brace with the top entry of the stack. These delimiters correspond, so we pop the stack. We have
reached the end of the expression, and the stack is empty. Each open delimiter correctly corre-
sponds to a close delimiter, so the delimiters are balanced.
5.7
Examples: Unbalanced expressions.
Let's examine some expressions that contain unbalanced
delimiters. Figure 5-4 shows a stack during the scan of an expression that contains the delimiters
{ [ ( ] ) }. This is an example of intersecting pairs of delimiters. After we push the first three open
delimiters onto the stack, the open parenthesis at the top of the stack does not correspond to the
close bracket that comes next in the expression.
FIGURE 5-4
The contents of a stack during the scan of an expression that
contains the unbalanced delimiters { [ ( ] ) }
Delimiters are not a pair
{
(
]
(
[
Delimiters in expression
Delimiter popped from stack
(
[
{
[
[
{
{
{
After
push('{')
After
push('[')
After
push('(')
After
pop()
Figure 5-5 shows a stack during the scan of an expression that contains the unbalanced delimiters
[ ( ) ] }. The close brace does not have a corresponding open brace. When we finally reach the close
brace, the stack is empty. Since the stack does not contain an open brace, the delimiters are unbalanced.
FIGURE 5-5
The contents of a stack during the scan of an expression that
contains the unbalanced delimiters [ ( ) ] }
A pair of parentheses
A pair of brackets
[
(
)
(
]
[
}
Delimiters in expression
Delimiters popped from stack
(
[
[
[
Stack is empty when
}
is encountered
After
push('[')
After
push('(')
After
pop()
After
pop()
