Problem statement

You are keeping the score for a baseball game with strange rules. You are given a list of strings operations, applied in order:

• an integer x — record a new score of x;
• "+" — record a new score that is the sum of the previous two scores;
• "D" — record a new score that is double the previous score;
• "C" — invalidate the previous score and remove it.

Return the sum of all the scores on the record after applying every operation.

Example 1

Input: operations = ["5","2","C","D","+"]
Output: 30
Explanation: The record ends as 5, 10, 15.

Example 2

Input: operations = ["5","-2","4","C","D","9","+","+"]
Output: 27

Example 3

Input: operations = ["1"]
Output: 1

Constraints

• 1 <= operations.length <= 20
• operations[i] is "C", "D", "+", or an integer in [-30000, 30000].
• Every operation is valid when it is applied.

Hints for Baseball Game

1. Hint 1

   The record behaves exactly like a stack: C pops, everything else pushes.

2. Hint 2

   + and D read the top of the stack without removing it.

3. Hint 3

   Sum the stack once every operation has been applied.

How to solve Baseball Game

The record is a stack: C pops, + and D read the top one or two entries and push a new value, a number pushes itself.

Approach

1. For each operation, push the number, push top + second, push 2 · top, or pop.
2. Return the sum of the stack.

Why it works

Every operation refers only to the most recent scores, so last-in-first-out is exactly the right structure.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• + needs two entries on the stack; the input guarantees they exist.

Reference solution

Python

def calPoints(operations) -> int:
    stack = []
    for op in operations:
        if op == "+":
            stack.append(stack[-1] + stack[-2])
        elif op == "D":
            stack.append(2 * stack[-1])
        elif op == "C":
            stack.pop()
        else:
            stack.append(int(op))
    return sum(stack)

Java

public static int calPoints(String[] operations) {
    List<Integer> stack = new ArrayList<>();
    for (String op : operations) {
        if (op.equals("+")) {
            stack.add(stack.get(stack.size() - 1) + stack.get(stack.size() - 2));
        } else if (op.equals("D")) {
            stack.add(2 * stack.get(stack.size() - 1));
        } else if (op.equals("C")) {
            stack.remove(stack.size() - 1);
        } else {
            stack.add(Integer.parseInt(op));
        }
    }
    int sum = 0;
    for (int x : stack) sum += x;
    return sum;
}

C++

int calPoints(vector<string>& operations) {
    vector<int> stack;
    for (const string& op : operations) {
        if (op == "+") stack.push_back(stack[stack.size() - 1] + stack[stack.size() - 2]);
        else if (op == "D") stack.push_back(2 * stack.back());
        else if (op == "C") stack.pop_back();
        else stack.push_back(stoi(op));
    }
    int sum = 0;
    for (int x : stack) sum += x;
    return sum;
}

JavaScript

var calPoints = function(operations) {
    const stack = [];
    for (let i = 0; i < operations.length; i++) {
        const op = operations[i];
        if (op === "+") stack.push(stack[stack.length - 1] + stack[stack.length - 2]);
        else if (op === "D") stack.push(2 * stack[stack.length - 1]);
        else if (op === "C") stack.pop();
        else stack.push(parseInt(op, 10));
    }
    let sum = 0;
    for (let i = 0; i < stack.length; i++) sum += stack[i];
    return sum;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy