731 views
2 votes
2 votes
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)$?

2 Answers

Best answer
8 votes
8 votes
$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$.
selected by
0 votes
0 votes

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.
Answer:

Related questions

0 votes
0 votes
1 answer
3
Arjun asked Oct 10, 2016
405 views
The postfix expression for the infix expression$$A + B*C/D +E$$isAB+*CD/E+ABC*D/+E+AB+C*D/E+A+*BCD/E+
0 votes
0 votes
2 answers
4
Arjun asked Oct 10, 2016
482 views
Which of the following permutation can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $1, 2, 3, 4$ in that order?3, 4...