in DS edited by
2,948 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. $()()$
in DS edited by
2.9k views

3 Comments

what does
s= empty  statement mean ?
0
0
Notice --> Difference between option B and D.
2
2
i am confused in i value here for i =6 it will terminate ?
0
0

5 Answers

20 votes
20 votes
Best answer

(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

2 Comments

When '(' is coming and '(' is already present as the top of stack why you are pushing '(' since it is not mentioned in the code to push it. Please explain
0
0

@rajatmyname , check the code again 5th line is pushing element in stack for every iteration.

0
0
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
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

4 Comments

brother, a little explanation would work better. : )
1
1
2
2
edited by
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 :)
3
3
Sure.. will keep that in mind next time! :)
0
0
Answer:

Related questions