3. (12 points total) Assume you have an initially empty Stack and a string of N

Question

3. (12 points total) Assume you have an initially empty Stack and a string of N characters. A program performs N push operations of each of those characters in the order in which they appear in the string. After each push, it performs any number of pop operations, such that the total number of pops is N. Assume that the pop operation prints the value that came off. For example, you could have the string:

LEMONS

Then you perform the following sequence of pushes and pops

push(L), push(E), push(M), pop(), pop(), pop(), push(O), pop(), push(N), pop(), push(S), pop()

It would result in the following output string:

MELONS

Now, consider the string:

RESCUED

For following two output strings, provide the sequence of stack operations that would
generate it from the initial string of RESCUED. If the sequence cannot occur, explain
why.
a. SECURED
b. REDUCES

Explanation / Answer

PLEASE GIVE THUMBS UP, FOR ANY QUERY LEAVE COMMENT, THANKS

SECURED is possible

PUSH(R),PUSH(E),PUSH(S),POP(S),POP(E),PUSH(C),POP(C),PUSH(U),POP(U),POP(R),PUSH(E),POP(E),PUSH(D),POP(D)

REDUCES is not possible .

Explanation: if we pop first E After poping R, then after S the stack top will be E,so we can't C without popping E so it will give sequence RESECUD. If we pop second E after popping R then, stack top will contain E, therefore E will poped after S so it will give sequence REDUCSE. SO b is not possible

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.