Approach: Stack simulation

def calPoints(s):
    st = []
    for tok in s.split():
        if tok == "C": st.pop()
        elif tok == "D": st.append(2*st[-1])
        elif tok == "+": st.append(st[-1]+st[-2])
        else: st.append(int(tok))
    return sum(st)

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

Full Solution — all languages

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

import java.util.*;
class Solution {
    public int calPoints(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        for (String tok : s.trim().split("\\s+")) {
            if (tok.equals("C")) st.pop();
            else if (tok.equals("D")) st.push(2 * st.peek());
            else if (tok.equals("+")) {
                int a = st.pop();
                int b = a + st.peek();
                st.push(a);
                st.push(b);
            } else st.push(Integer.parseInt(tok));
        }
        int sum = 0;
        for (int x : st) sum += x;
        return sum;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int calPoints(string s) {
        vector<int> st;
        stringstream ss(s);
        string tok;
        while (ss >> tok) {
            if (tok == "C") st.pop_back();
            else if (tok == "D") st.push_back(2 * st.back());
            else if (tok == "+") st.push_back(st[st.size()-1] + st[st.size()-2]);
            else st.push_back(stoi(tok));
        }
        int sum = 0;
        for (int x : st) sum += x;
        return sum;
    }
};

/**
 * @param {string} s
 * @return {number}
 */ var calPoints = function(s) {
    const st = [];
    for (const tok of s.split(/\s+/).filter(x => x.length)) {
        if (tok === 'C') st.pop();
        else if (tok === 'D') st.push(2 * st[st.length - 1]);
        else if (tok === '+') st.push(st[st.length - 1] + st[st.length - 2]);
        else st.push(parseInt(tok, 10));
    }
    return st.reduce((a, b) => a + b, 0);
};

Baseball Game

Example 1

Example 2

Constraints