392 views
A function $f$ defined on stack of integer satisfies the following properties:

$f(\{\}) = 1$ and

$f(PUSH(S,i)) = \max (f(S),1) * i$ for all stacks $S$ and integer $i$.

If a stack $S$ contains the integers $4, -2, 9$ in order from bottom to top, what is $f(S)$?

$f$ is defined on a stack and its value changes on a push operation.

Initially $f(S) = 1$ when no element is present.

After first push, 4, $f(S) =\max(1,1) \times 4 = 4$.

After second push, -2, $f(S) = \max(4,1) \times -2 = -8$.

After third push, 9, $f(S) = \max(-8, 1) \times 9 = 9$.
by

Initially f(S)=1 when stack is empty .rt?
Thanks. Corrected..
@Arjun sir,

How can we see that f(S) = 1, its not mentioned in the question.

Also, how have you taken f(S) = max(f(S),1)*i, in the question, its mentioned that f(PUSH(S,i)) = max(f(S),1)*i

f({})=1

=> When S is empty, this function value is 1.

We have to push 4, -2 and 9 in this empty stack so that the given stack configuration in the question is achieved.

• When pushing 4; max (1,1)*4 = 4
So, f(S) = 4 now.

• When pushing -2; max(4,1)*-2 = -8
So, f(S) = -8 now.

• When pushing 9; max(-8,1)*9 = 9
So, f(S) = 9 now.