The Gateway to Computer Science Excellence
+7 votes

Given finite alphabet S = {A, B, C} and stack S of size 100. There are only three stack operations we can perform as mentioned below.

Stack is initially empty and we do not perform pop ( ) on empty stack. Assume that only emit ( ) can print output and stack may or may not be empty finally. The minimum number of stack operations to get “A B C A C B A” as output are ______.

I am getting 15 but it is given 14. Please help.

in DS by
recategorized by | 325 views


 Stack may or may not be empty finally

Don`t pop $A$ after emitting.

$1) $Push A

Emit A $:A$

Push B
Emit B $:AB$

Push C
Emit C $:ABC$

Push A
Emit A $:ABCA$
Pop A
Emit C $ABCAC$
Pop C
Pop B
$14)$ Emit A $ABCACBA$

The set is {A,B,C}. So we have only instance of each of them right? I mean 1 A, 1 B and 1 C. If we don't pop the A for the 1st time after push and emit, how can we push it in the 7th step? It is already there in the stack ?
Maybe i am wrong! but i don`t think that way ! $S$ is an alphabet whereas $\{A,B,C\}$ are symbols finite alphabet means finite symbols to represent a given string  : one such given in question to represent.
I'm doing one instance each and getting solution as 16!


By set here we mean domain of choice (like in alphabet in  TOC). So we can have multiple instances of it.

Oh..but I thought in a set we don't have repetitions of elements unless it is a nultiset.

Please log in or register to answer this question.

Related questions

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
52,375 questions
60,554 answers
95,374 users