Baseball Game
Problem
Process tokens: integer (record), '+' (last two summed), 'D' (last doubled), 'C' (remove last). Return final score sum.
ops=['5','2','C','D','+']30def cal_points(ops):
s = []
for o in ops:
if o == '+': s.append(s[-1] + s[-2])
elif o == 'D': s.append(2 * s[-1])
elif o == 'C': s.pop()
else: s.append(int(o))
return sum(s)function calPoints(ops) {
const s = [];
for (const o of ops) {
if (o === '+') s.push(s[s.length-1] + s[s.length-2]);
else if (o === 'D') s.push(2 * s[s.length-1]);
else if (o === 'C') s.pop();
else s.push(+o);
}
return s.reduce((a, b) => a + b, 0);
}int calPoints(String[] ops) {
Deque s = new ArrayDeque<>();
for (String o : ops) {
if (o.equals("+")) { int a = s.pop(); int b = s.peek(); s.push(a); s.push(a + b); }
else if (o.equals("D")) s.push(2 * s.peek());
else if (o.equals("C")) s.pop();
else s.push(Integer.parseInt(o));
}
int total = 0; for (int x : s) total += x; return total;
} int calPoints(vector& ops) {
vector s;
for (auto& o : ops) {
if (o == "+") s.push_back(s.back() + s[s.size()-2]);
else if (o == "D") s.push_back(2 * s.back());
else if (o == "C") s.pop_back();
else s.push_back(stoi(o));
}
int total = 0; for (int x : s) total += x; return total;
} Explanation
This problem is really just a running list of scores, and a stack is the perfect tool because every special command only touches the most recent entries.
We walk through the tokens one by one and keep a stack s of recorded scores. A plain number gets pushed. 'C' cancels the last score, so we pop(). 'D' doubles the last score, so we push 2 * s[-1]. '+' records the sum of the last two, so we push s[-1] + s[-2].
Because the stack always has the latest scores on top, "last" and "second-to-last" are instantly available. At the end we just add up everything still on the stack.
Example: ['5','2','C','D','+']. Push 5 → [5]. Push 2 → [5,2]. 'C' pops 2 → [5]. 'D' pushes 10 → [5,10]. '+' pushes 15 → [5,10,15]. Sum is 30.
Each token is handled in constant time, so the whole thing is a single linear pass.