Consider the problem description below: an algorithm balancedBracketsByCounting(

Question

Consider the problem description below:
an algorithm balancedBracketsByCounting(String s), as follows, that takes a string
as an input and checks whether the brackets [" and ]" in the string are matched correctly. He
claimed that his algorithm is correct. For example, balancedBracketsByCounting("[x][[xy]]")
would return true but balancedBracketsByCounting("[[x[y]]") would return false.

This is the algorithm:
boolean balancedBracesByCounting(String s) {
numOfLeftBracketRound = 0; numOfRightBracketRound = 0
numOfLeftBracketSquare = 0; numOfRightBracketSquare = 0
balanced = true
while (not at the end of the s) {
if (the next character is an open bracket '(' {
numOfLeftBracketRound++
}
else if (the next character is an open bracket '[') {
numOfLeftBracketSquare++
else if (the next character is a close bracket ')' {
numOfRightBracketRound- -
} else if (the next character is a close bracket ']') {
numOfRightBracketSquare- -
}
}
return {(noOfLeftBracketRound==noOfRightBracketRound)
and (noOfLeftBracketSquare==noOfRightBracketSquare)}
}

Questions: why this algorithm is flawed, the errors and how to come up with a correct algorithm

Explanation / Answer

please rate - thanks

This is the algorithm:
boolean balancedBracesByCounting(String s) {
numOfLeftBracketRound = 0; numOfRightBracketRound = 0
numOfLeftBracketSquare = 0; numOfRightBracketSquare = 0
balanced = true
while (not at the end of the s) {
if (the next character is an open bracket '(' {                               the problem is this just "counts" the brackets
numOfLeftBracketRound++                                                           every time it gets an open it adds it, and when
}                                                                                                it gets a close it subtracts, so if there are the
else if (the next character is an open bracket '[') {                  same number of opens and corresponding closes                    the open count will be n and the close count
numOfLeftBracketSquare++                                                             will be -n, so a true would never be
else if (the next character is a close bracket ')' {                     returned.
numOfRightBracketRound- -                                                    
} else if (the next character is a close bracket ']') {
numOfRightBracketSquare- -
}
}
return {(noOfLeftBracketRound==noOfRightBracketRound)
and (noOfLeftBracketSquare==noOfRightBracketSquare)}
}

I think he meant to add when a right bracket was found, so that lefts and rights would be equal but then things like )(][ and ([)] would be considered balanced

to correct this you could use a stack

on an open bracket push into the stack, on a close bracket, pop from the stack and if they do not correspond to each other return false. also return false if the stack is empty when you go to do a pop or if there is something in the stack when the string is exhausted.

if the string is exhausted and the stack is empty return a true

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.