We have an implementation that supports the following operations on a stack (in the instructions below, $\mathsf{s}$ is the name of the stack).
- $\mathsf{isempty(s)}$ : returns $\mathsf{True}$ if $\mathsf{s}$ is empty, and $\mathsf{False}$ otherwise.
- $\mathsf{top(s)}$ : returns the top element of the stack, but does not pop the stack; returns $\mathsf{null}$ if the stack is empty.
- $\mathsf{push(s,x)}$ : places $\mathsf{x}$ on top of the stack.
- $\mathsf{pop(s)}$ : pops the stack; does nothing if $\mathsf{s}$ is empty.
Consider the following code:
pop_ray_pop(x):
s=empty
for i=1 to length(x):
if (x[i] == '('):
push(s, x[i])
else:
while (top(s)=='('):
pop(s)
end while
push(s, ')')
end if
end for
while not isempty(s):
print top(s)
pop(s)
end while
What is the output of this program when
pop_ray_pop("(((()((())((((")
is executed?
- ((((
- ))) ((((
- )))
- (((()))
- ()()