StackStats | Topcoder Archive

Problem Statement

When checking code in a stack based system, the verifier must often simulate stack accesses, as if the code was actually being run. This way it can verify all such stack interactions are legal, and can perhaps suggest optimizations. The current system being tested has memory separated into slots. Initially slot 0 is the top of the stack. Everytime a PUSH instruction is performed, the top of the stack moves one slot higher. Everytime a POP instruction is performed, the top of the stack moves one slot lower. After each instruction is executed, you record where the top of the stack is. Given a String[] instructions you will return a int[] describing how the stack was used. Element j of the return value should contain the number of instructions after which slot j was the top of the stack. The returned int[] should contain an entry for every slot visited by the top of the stack.

Definition

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

Constraints

commands will contain between 1 and 50 elements inclusive.
Each element of commands will be (quotes for clarity): "PUSH" or "POP".
The POP instruction will never be executed while the top of the stack is slot 0.

Examples

```
{"PUSH"}
```
```
Returns: { 0,  1 }
```
The top begins at slot 0. After the first and only instruction is executed the top is at slot 1. The return shows that slot 1 was the top after 1 instruction. Slot 0, although initially the top of the stack, was not the top after an instruction was executed.
```
{"PUSH","POP"}
```
```
Returns: { 1,  1 }
```
Now both slots 0 and 1 were the top after an instruction had executed.
```
{"PUSH","PUSH","PUSH","PUSH","POP","POP","POP","POP"}
```
```
Returns: { 1,  2,  2,  2,  1 }
```
The top of the stack was at the following slots in order: 0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0

{"PUSH","POP","PUSH","POP","PUSH","POP","PUSH","POP",
 "PUSH","POP","PUSH","POP","PUSH","POP","PUSH","POP",
 "PUSH","POP","PUSH","POP","PUSH","POP","PUSH","POP",
 "PUSH","POP","PUSH","POP","PUSH","POP","PUSH","POP",
 "PUSH","POP","PUSH","POP","PUSH","POP","PUSH","POP",
 "PUSH","POP","PUSH","POP","PUSH","POP","PUSH","POP",
 "PUSH","POP"}

Returns: { 25,  25 }

{"PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH",
 "PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH",
 "PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH",
 "PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH",
 "PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH",
 "PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH",
 "PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH","PUSH"}

Returns: { 0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  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.