# LeetCode 682: Baseball Game

## Problem Restatement

We are given a list of operations called `ops`.

These operations describe scores in a baseball game.

We process the operations from left to right and maintain a record of valid scores.

The operations are:

| Operation | Meaning |
|---|---|
| Integer `x` | Record a new score `x` |
| `"+"` | Record a score equal to the sum of the previous two valid scores |
| `"D"` | Record a score equal to double the previous valid score |
| `"C"` | Remove the previous valid score |

After processing all operations, return the sum of all valid scores.

The official examples include `["5","2","C","D","+"] -> 30` and `["5","-2","4","C","D","9","+","+"] -> 27`. ([leetcode.com](https://leetcode.com/problems/baseball-game/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of strings `ops` |
| Output | Integer total score |
| Valid operations | Integer, `"+"`, `"D"`, `"C"` |
| Guarantee | Operations are always valid |

Example function shape:

```python
def calPoints(ops: list[str]) -> int:
    ...
```

## Examples

Example 1:

```python
ops = ["5", "2", "C", "D", "+"]
```

Process step by step:

| Operation | Scores | Explanation |
|---|---|---|
| `"5"` | `[5]` | Record 5 |
| `"2"` | `[5, 2]` | Record 2 |
| `"C"` | `[5]` | Remove 2 |
| `"D"` | `[5, 10]` | Double previous score 5 |
| `"+"` | `[5, 10, 15]` | Sum of 5 and 10 |

Final sum:

```text
5 + 10 + 15 = 30
```

Answer:

```python
30
```

Example 2:

```python
ops = ["5","-2","4","C","D","9","+","+"]
```

Process:

| Operation | Scores |
|---|---|
| `"5"` | `[5]` |
| `"-2"` | `[5, -2]` |
| `"4"` | `[5, -2, 4]` |
| `"C"` | `[5, -2]` |
| `"D"` | `[5, -2, -4]` |
| `"9"` | `[5, -2, -4, 9]` |
| `"+"` | `[5, -2, -4, 9, 5]` |
| `"+"` | `[5, -2, -4, 9, 5, 14]` |

Final sum:

```text
5 - 2 - 4 + 9 + 5 + 14 = 27
```

Answer:

```python
27
```

## First Thought: Maintain All Valid Scores

Every operation only depends on recent valid scores.

For example:

| Operation | Depends on |
|---|---|
| `"D"` | Previous valid score |
| `"+"` | Previous two valid scores |
| `"C"` | Most recent valid score |

This naturally suggests a stack.

The stack stores all current valid scores in order.

The top of the stack is the most recent valid score.

## Key Insight

The operations exactly match stack behavior.

| Operation | Stack action |
|---|---|
| Integer | Push value |
| `"C"` | Pop top |
| `"D"` | Push `2 * top` |
| `"+"` | Push `top + second_top` |

Because each operation modifies only the most recent scores, we never need random access to older elements.

A stack gives efficient push and pop operations.

## Algorithm

Create an empty stack called `scores`.

Process each operation `op` in `ops`.

If `op` is an integer:

```python
scores.append(int(op))
```

If `op == "C"`:

```python
scores.pop()
```

If `op == "D"`:

```python
scores.append(scores[-1] * 2)
```

If `op == "+"`:

```python
scores.append(scores[-1] + scores[-2])
```

After processing all operations:

```python
return sum(scores)
```

## Walkthrough

Consider:

```python
ops = ["5", "2", "C", "D", "+"]
```

Start:

```text
scores = []
```

Operation `"5"`:

```text
scores = [5]
```

Operation `"2"`:

```text
scores = [5, 2]
```

Operation `"C"` removes the most recent score:

```text
scores = [5]
```

Operation `"D"` doubles the previous score:

```text
5 * 2 = 10
```

Now:

```text
scores = [5, 10]
```

Operation `"+"` sums the last two scores:

```text
5 + 10 = 15
```

Now:

```text
scores = [5, 10, 15]
```

Final result:

```text
5 + 10 + 15 = 30
```

## Correctness

The algorithm maintains the invariant that `scores` always contains exactly the valid scores after processing the current prefix of operations.

Initially, before processing any operation, the list is empty, which is correct.

If the next operation is an integer `x`, the rules say to record a new score `x`. The algorithm appends `x` to the stack, so the stack remains correct.

If the next operation is `"C"`, the rules say to invalidate the previous valid score. The most recent valid score is the top of the stack, so removing it with `pop()` produces the correct remaining scores.

If the next operation is `"D"`, the rules say to record double the previous valid score. The previous valid score is the top of the stack, so appending `2 * scores[-1]` records the correct new score.

If the next operation is `"+"`, the rules say to record the sum of the previous two valid scores. Those are the top two stack elements, so appending their sum records the correct new score.

Thus, after every operation, the stack exactly matches the valid scores defined by the problem statement.

At the end, the required answer is the total of all valid scores, which the algorithm returns using `sum(scores)`.

Therefore, the algorithm is correct.

## Complexity

Let `n` be the number of operations.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each operation is processed once |
| Space | `O(n)` | The stack may contain all recorded scores |

Each stack operation is constant time.

## Implementation

```python
class Solution:
    def calPoints(self, ops: list[str]) -> int:
        scores = []

        for op in ops:
            if op == "C":
                scores.pop()
            elif op == "D":
                scores.append(scores[-1] * 2)
            elif op == "+":
                scores.append(scores[-1] + scores[-2])
            else:
                scores.append(int(op))

        return sum(scores)
```

## Code Explanation

We store valid scores in:

```python
scores = []
```

For each operation:

```python
for op in ops:
```

If the operation is `"C"`:

```python
scores.pop()
```

we remove the most recent valid score.

If the operation is `"D"`:

```python
scores.append(scores[-1] * 2)
```

we double the previous valid score and record it.

If the operation is `"+"`:

```python
scores.append(scores[-1] + scores[-2])
```

we add the last two valid scores.

Otherwise, the operation is an integer string:

```python
scores.append(int(op))
```

Finally:

```python
return sum(scores)
```

returns the total score.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.calPoints(["5", "2", "C", "D", "+"]) == 30
    assert s.calPoints(["5","-2","4","C","D","9","+","+"]) == 27
    assert s.calPoints(["1"]) == 1
    assert s.calPoints(["1", "D"]) == 3
    assert s.calPoints(["1", "2", "+"]) == 6
    assert s.calPoints(["10", "-5", "D"]) == -5
    assert s.calPoints(["3", "C", "4"]) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `["5", "2", "C", "D", "+"]` | `30` | Official example |
| `["5","-2","4","C","D","9","+","+"]` | `27` | Official example with negative values |
| `["1"]` | `1` | Single score |
| `["1", "D"]` | `3` | Doubling operation |
| `["1", "2", "+"]` | `6` | Sum of previous two scores |
| `["10", "-5", "D"]` | `-5` | Double negative value |
| `["3", "C", "4"]` | `4` | Cancellation removes previous score |