Here is an incorrect pseudo code for an algorithm which is supposed to determine
ID: 3581438 • Letter: H
Question
Here is an incorrect pseudo code for an algorithm which is supposed to determine whether a String of parentheses is balanced: Give an example of an input string that is made up of only the characters ’(’ and ’)’, is unbalanced, but for which this algorithm will return true. Explain what is wrong with the algorithm. Can this algorithm ever incorrectly return false when its input string is a balanced string?
boolean isBlanced( String input )
{
declare a character stack
while ( input has more characters )
{
read a character from input
if ( the character is a ’(’ )
push it on the stack
else if ( the stack is not empty )
pop a character off the stack
else
return false
}
return true
}
Explanation / Answer
Whenever we are reading a character we are either pushing if it is '(' and popping without checking if it is ')' or not. We need to add that to the else if condition.
This algorith will return true for "()(". Because in the end we are not checking whether the stack is empty or not before returning true. We should do that in the end, if the stack is not empty we should return false.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.