On a stack machine, operations such as addition and multiplication take their arguments
from the top of the stack and push their results back onto the top of the stack. For example,
the expression (5+6)*(8-2) would be evaluated by the commands:
Push 5
Push 6
Add // pops 5 and 6, pushes 11
Push 8
Push 2
Subtract // pops 8 and 2, pushes 6
Multiply // pops 11 and 6, pushes 66
The cost of a sequence of commands is the maximum number of stack slots that are occupied at some point during the
execution of the commands. For example, the cost of the above sequence of commands is 3, achieved immediately after
pushing the 2, at which point the stack contains the values 11, 8, and 2. Our goal will be to minimize the cost of a sequence
of commands.
The only tool at our disposal is the swap command, which swaps the top two values on the stack. Consider, for example, the
following commands for evaluating the expression 9-2*3:
Push 9
Push 2
Push 3
Multiply // pops 2 and 3, pushes 6
Subtract // pops 9 and 6, pushes 3
The cost of this sequence is 3. Alternatively, we can achieve a cost of 2 by using the swap command:
Push 2
Push 3
Multiply // pops 2 and 3, pushes 6
Push 9
Swap // swaps 6 and 9
Subtract // pops 9 and 6, pushes 3
In essence, the swap command allows us to evaluate the right-hand argument of a binary operation before the
left-hand argument, whenever it is advantageous to do so. The values of the arguments are then on the stack
in the wrong order, so the swap command is used to put them in the correct order. (For commutative operations, such as addition,
the order of the arguments does not matter, but we will never use this fact.)
Notice that it is never advantageous
to use a swap command to exchange arguments of different binary operations. For example, it would be
pointless to rewrite the above commands as
Push 2
Push 9
Swap // swaps 2 and 9
Push 3
Multiply // pops 2 and 3, pushes 6
Subtract // pops 9 and 6, pushes 3
You will be given a String commands summarizing a sequence of commands with a '.' for each
push command, and a 'B' for each binary operation. For example, the commands for evaluating (5+6)*(8-2)
(shown at the beginning of the problem) would be represented as "..B..BB". The input is guaranteed to satisfy
the following grammar:
<cmds> = '.' | <cmds> <cmds> 'B'
You must determine the minimum cost that could be achieved for the input sequence of commands through judicious use of
swaps. You will return a int[] containing two elements: first the minimum cost and then the minimum number of
swap commands needed to achieve that cost. |