easy

Baseball Game

Keep a score record on a stack, where each operation records, cancels, doubles or sums the most recent scores.

1. Define the problem

Baseball Game

You are keeping score for a game. You get a list of operations, and you must return the sum of all scores on the record at the end. An operation is one of four things: a number records that score. C cancels the previous score and removes it. D records double the previous score. + records the sum of the previous two scores. A stack fits perfectly, because every operation only ever looks at or removes the most recent scores — exactly what the top of a stack gives you.

Constraints

  • 1 ≤ operations.length ≤ 1000
  • Each entry is an integer written as text, or 'C', 'D' or '+'
  • 'C' only appears when there is at least one score on the record
  • 'D' only appears when there is at least one score, and '+' only when there are at least two
  • The final total fits in a normal integer

Example

Inputoperations = ["5", "2", "C", "D", "+"]
Output30

Explanation Record 5, record 2, cancel the 2, double the 5 to get 10, then add 5 + 10 to get 15. The record holds 5, 10 and 15, which sum to 30.

2. Know the words first

In plain terms

Stack
A pile where you add and remove only at the top, so the most recent item is always the easiest one to reach.
Record
The running list of scores. Here it is the stack, bottom to top in the order they happened.
Cancel
Removing the most recent score from the record, as if it never happened.
3. Visualize the solution

The row is the score record, oldest on the left, newest on the right

The row is the score record, oldest on the left, newest on the right
Statusinit

The record starts empty, before any operation is read.

What happens in this step

operations = ["5", "2", "C", "D", "+"]
stack = []

Nothing is on the record yet, so every slot shows a dash.
Step 1 of 7

Steps to visualize

  1. Each filled cell is one score on the record. A dash means an empty slot.
  2. The frame marks the cell the current operation is touching.
  3. A number is pushed straight onto the top.
  4. C pops the top cell off. D pushes double the top. + pushes the sum of the top two.
  5. At the end, add up every filled cell to get the answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the score record, oldest on the left, newest on the right
Statusinit

The record starts empty, before any operation is read.

What happens in this step

operations = ["5", "2", "C", "D", "+"]
stack = []

Nothing is on the record yet, so every slot shows a dash.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function calPoints(operations) {
  const stack = [];

  for (const op of operations) {
    if (op === 'C') {
      stack.pop();
    } else if (op === 'D') {
      stack.push(stack[stack.length - 1] * 2);
    } else if (op === '+') {
      stack.push(stack[stack.length - 1] + stack[stack.length - 2]);
    } else {
      stack.push(Number(op));
    }
  }

  let total = 0;

  for (const score of stack) {
    total += score;
  }

  return total;
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
operations = ["5", "2", "C", "D", "+"]30example from the description
operations = ["7"]7smallest input, one score and nothing else
operations = ["3", "C"]0the only score is cancelled, leaving an empty record
operations = ["-2", "5", "+", "D"]12negative scores mixed with + and D
operations = ["5", "-2", "4", "C", "D", "9", "+", "+"]27a longer list using every operation
operations = ["1", "D", "D", "D"]15doubling over and over

Keep reading