The Gateway to Computer Science Excellence
+6 votes
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 ______.

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

in DS by Boss (22.8k points)
recategorized by | 237 views
+2

Keyword:  

 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
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 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.
0
I'm doing one instance each and getting solution as 16!
+1

 MiNiPanda

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.

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
50,650 questions
56,208 answers
194,077 comments
95,112 users