edited by
2,969 views
30 votes
30 votes

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?

  1. $(((($
  2. $))) \ (((($
  3. $)))$
  4. $(((()))$
  5. $()()$
edited by

5 Answers

Best answer
20 votes
20 votes

(D) is option.

First push  $(((($ on stack. Now when $)$ comes pop all $(((($ and push $)$ on stack. Now push $((($ and stack become $)((($ . Now when $)$ come it pop all $((($ from stack and new stack become $))$. Again $)$ comes and stack become $)))$ . Now push $(((($ on stack and the stack becomes $(((()))$. Now pop one by one and get option D as the answer.

edited by
7 votes
7 votes
Option D is correct
Whenver  " $ ) $ "  is found pop all  " $ ( $ " from stack .

$\begin{Vmatrix} \\ \\ \\ (\\ ( \\ ( \\ ( \end{Vmatrix}$    $\begin{Vmatrix} \\ \\ \\ (\\ ( \\ ( \\ ) \end{Vmatrix}$      $\begin{Vmatrix} ( \\ ( \\ ( \\ ( \\ ) \\ ) \\ ) \end{Vmatrix}$

Stack Figure 1 :  push $(((($  on $)$ pop  everything and then push $)$
Stack Figure 2 :  push $((($  on $)$ pop  everything and then push $)$
Stack Figure 3 :  push $ )$   and push $ ($
edited by
5 votes
5 votes
D, put proper inntentation to code. will increase readablity and thn can be solved easily.
operations going on -
if  "(" comes push it on stack

if ")" comes pop stack till it does not contain "(" on stack and then push ")"

after that. finally print whole stack.
4 votes
4 votes
Answer:

Related questions