Java Reference
In-Depth Information
5.9
Let's examine this algorithm for each of the examples given in the previous figures. For the balanced
expression in Figure 5-3, the
while
loop ends with an empty stack and
isBalanced
set to
true
. For
the expression in Figure 5-4, the loop ends when it finds that the close bracket does not correspond to
the open parenthesis. The flag
isBalanced
is
false
; the fact that the stack is not empty does not
affect the outcome of the algorithm.
With the expression in Figure 5-5, the loop ends at the close brace because the stack is empty
at that point. Retrieving or popping the top entry of the empty stack results in
null
, so the flag
isBalanced
is set to false. Finally, with the expression in Figure 5-6, the loop ends at the end of the
expression with
isBalanced
set to true. But the stack is not empty—it contains an open brace—so
after the loop,
isBalanced
becomes false.
Question 3
Show the contents of the stack as you trace the algorithm
checkBalance
, as
given in Segment 5.8, for each of the following expressions. What does
checkBalance
return in each case?
a.
[
a
{
b
/
(
c
-
d
)
+
e
/
(
f
+
g
)}
-
h
]
b.
{
a
[
b
+
(
c
+
2)
/
d
]
+
e
)
+
f
}
c.
[
a
{
b
+
[
c
(
d
+
e
)
-
f
]
+
g
}
5.10
Java implementation.
The class
BalanceChecker
, shown in Listing 5-2, implements our algorithm as
the static method
checkBalance
. The method has one parameter, the expression as a string. We assume
that the class
OurStack
implements
StackInterface
and is available. Since
StackInterface
specifies
a stack of objects, but the previous algorithm uses a stack of characters,
checkBalance
uses the wrapper
class
Character
to create objects suitable for the stack.
LISTING 5-2
The class
BalanceChecker
public class
BalanceChecker
{
/** Decides whether the parentheses, brackets, and braces
in a string occur in left/right pairs.
@param expression a string to be checked
@return true if the delimiters are paired correctly */
public static boolean
checkBalance(String expression)
{
StackInterface<Character> openDelimiterStack =
new
OurStack<Character>();
int
characterCount = expression.length();
boolean
isBalanced =
true
;
int
index = 0;
char
nextCharacter = ' ';
for
(; isBalanced && (index < characterCount); index++)
{
nextCharacter = expression.charAt(index);
