Statistics

Problem Statement for "StackMachine"

Problem Statement

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.

Definition

Class:
StackMachine
Method:
minimize
Parameters:
String
Returns:
int[]
Method signature:
int[] minimize(String commands)
(be sure your method is public)

Constraints

  • commands contains between 1 and 50 characters, inclusive.
  • commands contains only the characters '.' and 'B'.
  • commands satisfies the grammar = '.' | 'B'

Examples

  1. "...BB"

    Returns: { 2, 1 }

    The 9-(2*3) example above. By using one swap command, we can reduce the cost from 3 to 2.

  2. "..B..BB"

    Returns: { 3, 0 }

    The (5+6)*(8-2) example at the beginning of the problem. The cost is 3, and swaps do not help.

  3. ".......BBBBBB"

    Returns: { 2, 5 }

  4. "..B..BB..B..BBB....BBBB"

    Returns: { 4, 1 }

  5. "....B..BB..B..BBB..B..BB..B..BBBBBB"

    Returns: { 5, 2 }

  6. "..B.B..B...BB...BBB.B.B.BB...B.BBB...B.B..BB.BBBB"

    Returns: { 4, 3 }

  7. "..B..BB..B..BB..B..BBB..B..BB..B..BBBB..B..BBBB"

    Returns: { 5, 1 }

  8. ".........................BBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: { 2, 23 }

  9. "..B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B"

    Returns: { 2, 0 }

  10. "."

    Returns: { 1, 0 }

  11. "..B"

    Returns: { 2, 0 }

  12. "..B.B"

    Returns: { 2, 0 }

  13. "...BB.B"

    Returns: { 2, 1 }

  14. "...B.BB.B"

    Returns: { 2, 1 }

  15. "......BBBBB"

    Returns: { 2, 4 }

  16. "....BB.BB..BB"

    Returns: { 3, 1 }

  17. ".....BBB.B.B.BB"

    Returns: { 2, 3 }

  18. "..B..BB..B..B.BBB"

    Returns: { 4, 0 }

  19. "..B...B.B.B..BB.BBB"

    Returns: { 3, 2 }

  20. "...B..BBB...B.BBB..BB"

    Returns: { 3, 2 }

  21. "..B...BB..B.B..B.B.BBBB"

    Returns: { 3, 3 }

  22. "...BB..B..B...BBB..B.BBBB"

    Returns: { 3, 4 }

  23. "...B..B.BBB....BB.BBB...BBB"

    Returns: { 3, 4 }

  24. "..B....BBB.BB..B..B.B..B.BBBB"

    Returns: { 4, 2 }

  25. "..B.B.B..B..BB...B.BBBB..BB..BB"

    Returns: { 3, 2 }

  26. "..B..B...BB.BB.BB....BBB....BBBBB"

    Returns: { 4, 4 }

  27. "...BB..BB.B..B.BB...B..B.B..B.BBBBB"

    Returns: { 4, 2 }

  28. "...B.BB.B..BB...B.B.B...BBBB..B..BBBB"

    Returns: { 4, 2 }

  29. "..B...BBB..BB.B...B..BBBB..B.B..B..BBBB"

    Returns: { 4, 2 }

  30. "..B....BB..B.BB..BB.BBB..B...BB..B..BBBBB"

    Returns: { 4, 4 }

  31. "..B.B.B......BBBB.B....BBB.B..BBB..B.BBB.BB"

    Returns: { 3, 7 }

  32. "..B.B...BB.B...BB..B.BB..BB..B.B...BBBBBB..BB"

    Returns: { 4, 3 }

  33. "..B..B.B..B.BB..BBB...B..B.BBB...B.BB..BB.B.BBB"

    Returns: { 4, 2 }

  34. "..B...BB..BBB..B.BB...B.BB...BB..B..B.BB.BBB..BBB"

    Returns: { 4, 3 }

  35. ".....B..B...B.BBBBBBB...B.B..B..B.B.BBBB.B..BB.BB"

    Returns: { 4, 6 }

  36. "...B..B..BBB.BB..B.B....BBB..B.BBB....B.B..BBBBBB"

    Returns: { 4, 6 }

  37. "..B..BB..B...B..B.BBBB..BB..B...B.BB.BB..B..BBBBB"

    Returns: { 4, 4 }

  38. "..B.B..BB..BB....BBBB.B..B..BB..BB.....BB..BBBBBB"

    Returns: { 4, 5 }

  39. "...BB..BB..B...B.BB.BBB...BBB...BBB..B.B.B..B.BBB"

    Returns: { 4, 1 }

  40. "..B.B..B.B..BBB.B..BB..B...BB.B.BB..B..B..B.BBBBB"

    Returns: { 4, 3 }

  41. "..B...BBB....BBBB..B..BB..BB..B...BBBB.BB.B..B.BB"

    Returns: { 4, 5 }

  42. "...BB..B...BB..B.B..BBB....BBBB...B.BBBBB...BB.BB"

    Returns: { 3, 9 }

  43. "..B....BBBB..B..B.B..BBB..BBB..B.B..BB..B..BB.BBB"

    Returns: { 5, 0 }

  44. "...B..BB..BB.B..BBB.B...BB...BB..B.B..B..BB.BBBBB"

    Returns: { 4, 4 }

  45. "..B.B...B..BBB...BB..BBBB....BBBB.....BB..B.BBBBB"

    Returns: { 4, 4 }

  46. "...BB....BBB.B.BB.B..B..BB.BB..B..B.BB..B..BBBB.B"

    Returns: { 5, 0 }

  47. "...B....BB.B..BBB...BBBBB..B..B.B...BB.BBB..B.BBB"

    Returns: { 4, 4 }

  48. "..B..B..BBB..BB....B..BB..B.BBBBB..B..B.B.BB..BBB"

    Returns: { 4, 2 }

  49. "...BB.B....B.BBB..B..B.BB...B.BBBBB..BB...BB..BBB"

    Returns: { 4, 2 }

  50. "..B.B..B...BB..BB....BBB..B..B.B..B..BBB..BBBBBBB"

    Returns: { 4, 5 }

  51. "..B.B..B...BBB.B..B..BBBB..B..B..BB.BB..B..B.BBBB"

    Returns: { 5, 0 }

  52. "...B...BBB.B.B.BB..B..BB..B.BB..B.BB...BB..BB.BBB"

    Returns: { 4, 3 }

  53. "...BB...BBB..B...BBB.B...BB.BB.....BBBBB..B..BBBB"

    Returns: { 4, 4 }

  54. "..B...BBB...BB...BB.BB...BB..BB..BBBB..B.B..B.BBB"

    Returns: { 4, 2 }

  55. "..B..BB...BB..B..BBBB"

    Returns: { 4, 1 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: