Baseball Game
Easy · Stack & Strings · Array · Stack · Simulation
Problem
You are keeping score for a game with unusual rules. The scorecard starts empty, and you are given a list of strings operations, applied in order:
- an integer x records a new score of x;
- "+" records a new score equal to the sum of the previous two scores;
- "D" records a new score equal to double the previous score;
- "C" cancels the previous score, removing it from the card.
Return the sum of all scores left on the card after every operation has been applied. The operations are always valid: "+" always has two scores before it, and "C" and "D" always have at least one.
Examples
Input: operations = ["4","7","+","C","D"] Output: 25
The card goes 4, 7, 11; then 11 is canceled and 7 is doubled to 14, so the total is 4 + 7 + 14.
Input: operations = ["-2","D","+"] Output: -12
The scores are -2, -4 and -6.
Input: operations = ["5","3","C","D","+"] Output: 30
After the cancel the card is [5]; "D" adds 10 and "+" adds 15, so the total is 30.
Constraints
- 1 <= len(operations) <= 1000
- operations[i] is "C", "D", "+", or an integer in the range [-3 · 10^4, 3 · 10^4] written as a string
- Every score and the answer fit in a 32-bit integer
Approaches
- Baseline: list of scores, add them up at the end — time O(n), space O(n)
Follow-up
Could you report the total after every operation without adding up the card each time? Keep the running total, as the optimal solution does. See the use cases for those running totals, and for a log of folder moves where only the stack height matters.
Related problems
Start free on Cariara · Coding problems · System design studio
