Stack · LC #682
Baseball Game
Simulate a baseball scoring game with operations that add, double, cancel, or sum scores using a stack as the running record.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You keep score for a baseball game with unusual rules. Given a list of string operations: - An integer string: record a new score equal to that integer. - `"+"`: record a new score equal to the sum of the previous two scores. - `"D"`: record a new score equal to double the previous score. - `"C"`: invalidate the previous score, removing it from the record. Return the sum of all scores on the record after performing all operations.
Sample I/O
Input: ops = ["5","2","C","D","+"] Output: 30 Explanation: 5→[5], 2→[5,2], C→[5], D→[5,10], +→[5,10,15], sum=30 Input: ops = ["5","-2","4","C","D","9","+","+"] Output: 27
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
The scoring record is a history that supports undo (C) and transformations referencing recent values. A stack is the natural fit: push new scores, pop for undo, peek for the last one or two values needed by D and +.
Core Concept
Use a stack of integers representing the running record. Process each operation: integer strings are parsed and pushed; "C" pops the last score; "D" pushes double the current top; "+" requires peeking the top two - pop the first, peek the second, sum them, then push the popped value back and push the sum. Finally sum all remaining stack values.
When to use
Stack simulation problems where each step depends on recent history and undoing the last action is needed.
When NOT to use
Problems where operations depend on arbitrary positions in history rather than just the top one or two elements.
Key Insights
What to Know Cold
- For "+" you must peek the second-from-top: pop top, peek new top, push old top back, then push sum.
- Negative integer strings like "-2" are valid scores - use parseInt/int() not unsigned parsing.
- The problem guarantees "+" and "D" only appear when there are enough previous scores.
- Using a vector/array as a stack (C++) is simpler for indexed access when implementing "+".
- Sum at the end via stream/reduce avoids a manual loop.
1 example
Worked Examples
Step-by-step trace of ops = ["5","2","C","D","+"]
Walk through each operation and show the stack state after each step.
Push 5, push 2, pop on C, push 10 on D (double 5), push 15 on + (10+5). Sum = 5+10+15 = 30.
// Trace: // "5" → stack: [5] // "2" → stack: [5, 2] // "C" → stack: [5] // "D" → stack: [5, 10] // "+" → stack: [5, 10, 15] // sum → 30 calPoints(["5","2","C","D","+"]); // 30
Output: 30
Shows the classic "+" trap: you must preserve the top value while peeking the second, requiring a pop-peek-push-push sequence.