GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
125 views

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. ()()
asked in DS by Veteran (76k points)   | 125 views
what does
s= empty  statement mean ?

4 Answers

+5 votes
D 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.
answered by Active (1.3k points)  
+2 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 $ ($
answered by Veteran (20.2k points)  
edited by
+2 votes
answered by Active (1.3k points)  
brother, a little explanation would work better. : )
Thanks @srestha, :)

Actually, I wanted to tell this brother that please post your ans with little explanation. If he/she does not want to ans or not very sure about ans then write options in the comment.

No offense, please :)
Sure.. will keep that in mind next time! :)
+1 vote
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.
answered by Veteran (13.4k points)  


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,446 questions
26,759 answers
60,943 comments
22,955 users