CAPE Computer Science Unit 2 · 2005 · Paper 1 · Question 12(a)(ii)

The following algorithm accepts a string of characters and uses the stack abstract data type to process the characters one by one. The only characters in the string are '(' and ')'. Algorithm Mystery (String inputString): length <- number of characters in inputString create a new stack, stk For i = 1 to length do ch <- i-th character of inputString If ch is a left parenthesis, '(' Push ch onto stk Else If stk is empty then Print "Failure 1" Exit Algorithm Mystery Else Pop the topmost character from stk End if End if End for If stk is not empty then Print "Failure 2" Else Print "Success" End if End Algorithm Mystery

By showing each step in the processing of the input string, determine the output that the Mystery algorithm will generate given the input string: ( ( ) )