GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
197 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 (92.5k points) 964 2327 3113 | 197 views
what does
s= empty  statement mean ?

4 Answers

+9 votes
Best answer
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.5k points) 2 5 14
selected by
+3 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 (22.8k points) 46 216 358
edited by
+2 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.
answered by Veteran (15k points) 17 53 133
+2 votes
answered by Active (1.4k points) 2 10 31
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! :)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23338 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7912 Points

  4. srestha

    6228 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question makhdoom ghaya
Popular Question junaid ahmad
Notable Question learner_geek
Notable Question jothee
Popular Question jothee
Notable Question Jeffrey Jose
Notable Question air1ankit
Nice Question jothee
Verified Human shaleen25
Popular Question jothee
27,290 questions
35,142 answers
83,920 comments
33,231 users