in Programming recategorized by
511 views
2 votes
2 votes

A function f is defined on stack of integer satisfies the following properties .

f(empty) = 0 and f( PUSH(S,i) ) = max (f(S),0) + i   for all stacks S and integer i.

If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top ,  Then what is f(S)?

  1. 6
  2. 4
  3. 3
  4. 2
in Programming recategorized by
by
511 views

1 Answer

8 votes
8 votes
Best answer
f is defined on a stack and its value changes on a push operation.

Initially f(S)=0 when no element is present and f(empty)=0 as defined in the question.These elements are to be pushed into the stack in the same sequence 2,-3,2,-1,2, Below is the formula.

f(PUSH(S,i)) = max (f(S),0)+i

After first push, 2, f(S)=max(0,0) + 2 = 2.

After second push, -3, f(S)=max(2,0) + −3 = −1

After third push, 2, f(S)=max(−1,0) + 2 = 2

After fourth push, -1, f(S)=max(2,0) + -1 = 1

After fifth push, 2, f(S)=max(1,0) + 2 = 3

Therefore the answer is (C) 3
selected by
by
Answer:

Related questions