Java Reference
In-Depth Information
Although programmers use parentheses when writing arithmetic expressions in Java, mathema-
ticians use parentheses, square brackets, and braces for the same purpose. These delimiters must
be paired correctly. For example, an open parenthesis must correspond to a close parenthesis. In
addition, pairs of delimiters must not intersect. Thus, an expression can contain a sequence of
delimiters such as
{ [ ( ) ( ) ] ( ) }
but not
[ ( ] )
For convenience, we will say that a
balanced expression
contains delimiters that are paired cor-
rectly, or are
balanced
.
We want an algorithm that detects whether an infix expression is balanced.
5.6
Example: A balanced expression.
Let's see whether the expression
a
{
b
[
c
(
d
+
e
)
/
2
-
f
]
+
1}
is balanced. We scan the expression from left to right, looking for delimiters and ignoring any char-
acters that are not delimiters. When we encounter an open delimiter, we must save it. When we find
a close delimiter, we must see whether it corresponds to the most recently encountered open delim-
iter. If it does, we discard the open delimiter and continue scanning the expression. If we are able to
scan the entire expression without a mismatch, the delimiters in the expression are balanced.
The ADT that enables us to store objects and then retrieve or remove the most recent one is a
stack. Figure 5-3 shows the contents of a stack as we scan the previous expression. Since we ignore
all characters that are not delimiters, it is sufficient for us to represent the expression here as
{
[ ( ) ] }
FIGURE 5-3
The contents of a stack during the scan of an expression that
contains the balanced delimiters {
[ ( ) ] }
{
(
[
)
(
]
[
}
{
Delimiters in expression
Delimiters popped from stack
(
[
[
[
{
{
{
{
{
After
push('{')
After
push('[')
After
push('(')
After
pop()
After
pop()
After
pop()
