237 views

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 ______.

in DS
recategorized | 237 views
+2

Keyword:

Stack may or may not be empty finally

Dont 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
Emit B $ABCACB$
Pop B
$14)$ Emit A $ABCACBA$

0
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 ?
+1
Maybe i am wrong! but i dont 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.
0
I'm doing one instance each and getting solution as 16!
+1

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

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