GATE IT 2004 | Question: 52

Question

A program attempts to generate as many permutations as possible of the string, '$abcd$' by pushing the characters $a, b, c, d$ in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?

• A. $abcd$
• B. $dcba$
• C. $cbad$
• D. $cabd$

Comments

Similar concept : 

https://gateoverflow.in/2457/gate-cse-1994-question-1-14

---

https://gateoverflow.in/2457/gate-cse-1994-question-1-14#:~:text=How%20to%20do%20this%20within%20second%20%40%20GATE

Answer 1

• A. push $a$ & pop $a$, push $b$ & pop $b$, push $c$ & pop $c$, and finally push $d$ and pop $d$
  sequence of popped elements will come to $abcd$
• B. first push $abcd$, and after that pop one by one, sequence of popped elements will come to $dcba$
• C. push $abc$, and after that pop one by one sequence of popped elements will come to $cba$, now push $d$ and pop $d$, final sequence comes to $cbad$
• D. this sequence is not possible because '$a$' can not be popped before '$b$' any how

Comments

I have come to this solution ... Assume 'A' as 1 .. 'B' as 2... 'C' as 3... 'D' as 4 ... So it is 1234 ...  then apply this question's logic .... https://gateoverflow.in/2457/gate1994-1-14 ... U will get D as answer ...

---

@None ... what advantage did you get by doing that? It is a simple sequence of stack operations.

Answer 2

Option A :- abcd => ()()()()

Option B :- dcba => (((())))

Option C :- cbad => ((()))()

Option D :- cabd => Not Possible

Therefore, Correct Option is D) cabd

Answer 3

Anwser is in the uploaded image