+1 vote
96 views

Consider a stack S given below with elements 1,2,3 along with the usual operations push(), pop() and top() as shown. The number of elements that will remain in the stack after the parsing of the input string according to the above SDT rules is _______

I think the answer should be 5 but 4 is provided as answer.

in DS
recategorized | 96 views
0
Can you tell why it should be 5? Because there is one '/' operation which is performing pop so remaining element in stack are 2 and 2 'X' operation which are pushing 5 two times so total should be 4 elements in stack right?
0
If I construct a tree and traverse it - 1, 2 pushed then one element popped for B->C/D. - so 1 element remaining

then 3, 4 pushed and a 5 is pushed because of A->B*C - so now 4 elements in the stack

again a 5 is pushed for A->B*C.  So total 5 elements remaining.
+1
but in stack already elements(1,3,2) are present and while traversing tree when you'll get 1,2 then it is returning top() of stack not pushing in stack.
0
Oh, I didn't notice that. Thank You
0

@Shubhgupta

here element 4 is not pushed into the stack.

am I right?