Bracket Matching -> catching bad nesting

[mdchesne]

I have a program that is supposed to match brackets ( [,), and } ) but also correct nesting. I have the matching part done, but I can't seem to think of a way to check nesting. If the input string is: ([)] , my program as of now, will return "good" because there are equal number of closing brackets for an opening bracket of the same type, but the nesting arangement is bad. anyway I can do this?

should catch it as soon as the string closes out a bracket on the interior that is, itself, not closed:
( -> ( [ -> ( [ ) "Bad"
Edit/Delete Message

I'm thinking if I do a series of if statements, I could get it working. But I've been toying with if statements on paper for the past hour and if I do it this way, it'll be about 100 lines of code by itself!

(Code available for PM)

 

[MrChad]

A stack would work well for this.

1. Scan your string for open brackets ('(','[','{') and push them onto a stack as you find them.
2. When you come to a close bracket (')',']','}'), stop and pop the topmost item off of the stack.
3. The bracket you pop off the stack should match the close bracket you just found.
4. Repeat steps 1-3 until you reach the end of the string.

 

[mdchesne]

would that work though? I mean, using one stack, you can only pop the first element. so if you have ( [ ) ], it would push push, pop pop, and at the end, still read "good" cause the stack is empty (# opening brackets = # closing brackets). I'm using three stacks currently. one for parenthesis, one for brackets, and one for squiggle brackets, but that would only solve the problem of # of brackets.

 

[EpsiIon]

Well I was going to give you some hints until I reread MrChad's post and realized that he gave you the entire program in pseudocode.

 

[MrChad]

Originally posted by: EpsiIon
Well I was going to give you some hints until I reread MrChad's post and realized that he gave you the entire program in pseudocode.

I guess I did give away a lot. I always have trouble with where to draw the line on these HW threads.

 

[mdchesne]

so if I revert back down to only one stack, and make a simple if statement that checks if the closing brack it of the same type as the most recent opening one:

if (parens.top == s.charAt(i)) {pop;}
else { System.println ("bad"); }

it'll work. hmmm

test:
[ ( ] )

push --> push --> ] does not equal most recent push --> bad

[ [ [ ( { } ) ] ] ]

push push push push push pop pop pop pop pop --> good

[ ( ) )

push push pop (error) --> bad

[ ( ) { { } } ]

push push pop push push pop pop pop --> good

OMG, it works. I just used too many brackets and made if far more complicated than it needed to be. I'll also put the test at the end of the while loop to test if the stack is empty as well. thanks Chad!