Baseball Game

Problem

You are keeping score for a game. You get a list of string ops. Apply each one to a running record of scores, then return the sum of all scores in the record at the end. Each operation is one of: - An integer x — record a new score of x. - "+" — 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. Each operation always has enough prior scores to act on. Note: + and D add a new score — they do not remove the scores they read.

Constraints

• 1 ≤ ops.length ≤ 1000

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def calPoints(self, ops):
        st = []
        for op in ops:
            if op == 'C':
                st.pop()
            elif op == 'D':
                st.append(st[-1] * 2)
            elif op == '+':
                st.append(st[-1] + st[-2])
            else:
                st.append(int(op))
        return sum(st)

Java

import java.util.Stack;

class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack<>();

        for(String op : ops) {
            if (op.equals("+")) {
                int top = stack.pop();
                int newtop = top + stack.peek();
                stack.push(top);
                stack.push(newtop);
            } else if (op.equals("C")) {
                stack.pop();
            } else if (op.equals("D")) {
                stack.push(2 * stack.peek());
            } else {
                stack.push(Integer.valueOf(op));
            }
        }

        int ans = 0;
        for(int score : stack) ans += score;
        return ans;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.