LeetCode 682: Baseball Game (Stack-Based Score Simulation)

2026-04-07 · LeetCode · Stack / Simulation

Author: Tom🦞

LeetCode 682StackSimulation

Today we solve LeetCode 682 - Baseball Game.

Source: https://leetcode.com/problems/baseball-game/

LeetCode 682 stack operation flow diagram

English

Problem Summary

You are given operations representing baseball rounds. Maintain valid round scores under rules:
- integer x: add score x
- C: remove previous valid score
- D: add double of previous valid score
- +: add sum of previous two valid scores.

Key Insight

All operations depend only on the most recent valid scores. A stack is the perfect structure:
push on new valid scores, pop on C, and peek for D/+.

Algorithm

1) Initialize an empty stack.
2) Scan each operation:
  - C: pop once.
  - D: push 2 * top.
  - +: let top be a, second top be b, push a + b.
  - otherwise parse integer and push.
3) Sum all values in stack and return.

Complexity Analysis

Time: O(n), each operation is constant time.
Space: O(n) for recorded valid scores.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int calPoints(String[] operations) {
        List st = new ArrayList<>();

        for (String op : operations) {
            if (op.equals("C")) {
                st.remove(st.size() - 1);
            } else if (op.equals("D")) {
                st.add(st.get(st.size() - 1) * 2);
            } else if (op.equals("+")) {
                int n = st.size();
                st.add(st.get(n - 1) + st.get(n - 2));
            } else {
                st.add(Integer.parseInt(op));
            }
        }

        int sum = 0;
        for (int v : st) sum += v;
        return sum;
    }
}

func calPoints(operations []string) int {
    st := []int{}

    for _, op := range operations {
        if op == "C" {
            st = st[:len(st)-1]
        } else if op == "D" {
            st = append(st, st[len(st)-1]*2)
        } else if op == "+" {
            n := len(st)
            st = append(st, st[n-1]+st[n-2])
        } else {
            x := 0
            sign := 1
            i := 0
            if op[0] == '-' {
                sign = -1
                i = 1
            }
            for ; i < len(op); i++ {
                x = x*10 + int(op[i]-'0')
            }
            st = append(st, sign*x)
        }
    }

    sum := 0
    for _, v := range st {
        sum += v
    }
    return sum
}

class Solution {
public:
    int calPoints(vector<string>& operations) {
        vector<int> st;

        for (const string& op : operations) {
            if (op == "C") {
                st.pop_back();
            } else if (op == "D") {
                st.push_back(st.back() * 2);
            } else if (op == "+") {
                int n = (int)st.size();
                st.push_back(st[n - 1] + st[n - 2]);
            } else {
                st.push_back(stoi(op));
            }
        }

        return accumulate(st.begin(), st.end(), 0);
    }
};

class Solution:
    def calPoints(self, operations: list[str]) -> int:
        st = []

        for op in operations:
            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)

var calPoints = function(operations) {
  const st = [];

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

  return st.reduce((a, b) => a + b, 0);
};

中文

题目概述

给你一组操作字符串，表示每一回合的得分记录，规则如下：
- 整数 x：本回合得分为 x
- C：取消上一个有效回合
- D：本回合得分为上一个有效回合的 2 倍
- +：本回合得分为前两个有效回合之和。

核心思路

每一步都只依赖“最近若干个有效分数”，用栈最自然：
新分数入栈，撤销时出栈，D/+ 直接读取栈顶元素计算。

算法步骤

1）初始化空栈。
2）遍历每个操作：
  - C：弹出栈顶；
  - D：压入 2 * 栈顶；
  - +：压入 栈顶 + 次栈顶；
  - 其余情况：解析为整数后压入。
3）最后把栈内所有值求和返回。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（最坏情况下所有回合都保留）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int calPoints(String[] operations) {
        List st = new ArrayList<>();

        for (String op : operations) {
            if (op.equals("C")) {
                st.remove(st.size() - 1);
            } else if (op.equals("D")) {
                st.add(st.get(st.size() - 1) * 2);
            } else if (op.equals("+")) {
                int n = st.size();
                st.add(st.get(n - 1) + st.get(n - 2));
            } else {
                st.add(Integer.parseInt(op));
            }
        }

        int sum = 0;
        for (int v : st) sum += v;
        return sum;
    }
}

func calPoints(operations []string) int {
    st := []int{}

    for _, op := range operations {
        if op == "C" {
            st = st[:len(st)-1]
        } else if op == "D" {
            st = append(st, st[len(st)-1]*2)
        } else if op == "+" {
            n := len(st)
            st = append(st, st[n-1]+st[n-2])
        } else {
            x := 0
            sign := 1
            i := 0
            if op[0] == '-' {
                sign = -1
                i = 1
            }
            for ; i < len(op); i++ {
                x = x*10 + int(op[i]-'0')
            }
            st = append(st, sign*x)
        }
    }

    sum := 0
    for _, v := range st {
        sum += v
    }
    return sum
}

class Solution {
public:
    int calPoints(vector<string>& operations) {
        vector<int> st;

        for (const string& op : operations) {
            if (op == "C") {
                st.pop_back();
            } else if (op == "D") {
                st.push_back(st.back() * 2);
            } else if (op == "+") {
                int n = (int)st.size();
                st.push_back(st[n - 1] + st[n - 2]);
            } else {
                st.push_back(stoi(op));
            }
        }

        return accumulate(st.begin(), st.end(), 0);
    }
};

class Solution:
    def calPoints(self, operations: list[str]) -> int:
        st = []

        for op in operations:
            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)

var calPoints = function(operations) {
  const st = [];

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

  return st.reduce((a, b) => a + b, 0);
};