Consider the problem description below:
John proposed 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 John's algorithm:
Study carefully John's algorithm andboolean 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)} }
1. Explain why the algorithm balancedBracketsByCounting(String s) is
awed.
2. Demonstrate one
awed case in which, with the aid of an example of input, the algorithm may
return a true for a wrong match.
3. Identify as many errors or weaknesses as possible in John's algorithm, and correct or improve
them. Summarise your results in a table
4. Derive an alternative algorithm that would return correct answers. Show all your work.
5. Implement your algorithm, referring to the submission requirements.