Java Reference
In-Depth Information
Figure 5-6 shows a stack during the scan of an expression that contains the unbalanced delim-
iters { [ ( ) ]. The open brace does not have a corresponding close brace. When you reach the end of
the expression, having processed the brackets and parentheses, the stack still contains the open
brace. Since this delimiter is left over, the expression contains unbalanced delimiters.
FIGURE 5-6
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
(
[
[
[
{
{
{
{
{
{
Brace is left over in stack
After
push('{')
After
push('[')
After
push('(')
After
pop()
After
pop()
5.8
The algorithm.
The previous discussion and figures reveal the paths that our algorithm must take.
We formalize these observations in the following pseudocode:
Algorithm
checkBalance(expression)
//
Returns true if the parentheses, brackets, and braces in an expression are paired correctly
.
isBalanced =
true
while
((isBalanced ==
true
)
and not at end of
expression)
{
nextCharacter =
next character in
expression
switch
(nextCharacter)
{
case
'(':
case
'[':
case
'{':
Push
nextCharacter
onto stack
break
case
')':
case
']':
case
'}':
if
(
stack is empty
)
isBalanced =
false
else
{
openDelimiter =
top entry of stack
Pop stack
isBalanced =
true
or
false
according to whether
openDelimiter
and
nextCharacter
are a pair of delimiters
}
break
}
}
if
(
stack is not empty
)
isBalanced =
false
return
isBalanced
