GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
131 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 (77.2k points)   | 131 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.2k 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.3k 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.6k points)  


Top Users May 2017
  1. akash.dinkar12

    3154 Points

  2. pawan kumarln

    1636 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Bikram

    1298 Points

  6. Devshree Dubey

    1246 Points

  7. Angkit

    1044 Points

  8. Debashish Deka

    1042 Points

  9. LeenSharma

    880 Points

  10. srestha

    706 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    384 Points

  2. pawan kumarln

    262 Points

  3. Ahwan

    236 Points

  4. Arnab Bhadra

    136 Points

  5. LeenSharma

    118 Points


22,770 questions
29,090 answers
65,119 comments
27,635 users