5` 记录加 `5` ，记录现在是 `[5]` `2` 记录加 `2` ，记录现在是 `[5, 2]` `C` 使前一次得分的记录无效并将其移除，记录现在是 `[5]`. `D` 记录加 `2 * 5 = 10` ，记录现在是 `[5, 10]`. `+` 记录加 `5 + 10 = 15` ，记录现在是 `[5, 10, 15]`. 所有得分的总和 `5 + 10 + 15 = 30

示例二

输入

5 -2 4 C D 9 + +

输出

说明

5` 记录加 `5` ，记录现在是 `[5]` `-2` 记录加 `-2` ，记录现在是 `[5, -2]` `4` 记录加 `4` ，记录现在是 `[5, -2, 4]` `C` 使前一次得分的记录无效并将其移除，记录现在是 `[5, -2]` `D` 记录加 `2 * -2 = -4` ，记录现在是 `[5, -2, -4]` `9` 记录加 `9` ，记录现在是 `[5, -2, -4, 9]` `+` 记录加 `-4 + 9 = 5` ，记录现在是 `[5, -2, -4, 9, 5]` `+` 记录加 `9 + 5 = 14` ，记录现在是 `[5, -2, -4, 9, 5, 14]` 所有得分的总和 `5 + -2 + -4 + 9 + 5 + 14 = 27

示例三

输入

输出

示例四

输入

输出

-1

解题思路

注意，本题和LC682. 棒球比赛几乎完全一致。唯一的区别在于，本题需要考虑异常的存在，稍微增加了难度。

对于所有的输入，我们可以分为两类：

数字
操作符，包括"C"，"D"，"+"

这三种操作符，都是对最近的一次或两次得分进行操作。看到最近二字，我们应该马上想到使用后进先出LIFO的栈来解题，本质上也是一道表达式求值/化简类型的栈题。

我们首先构建一个空栈stack，然后遍历ops数组中的字符串record，对不同类型的record进行不同操作：

遇到数字型字符串：直接数字入栈，要注意将字符串类型str转化为整数类型int。

if record.isdigit():
    stack.append(int(record))

遇到"D"：将栈顶元素的两倍入栈，要注意判断此时栈中元素个数len(stack)是否大于等于1。

if record == 'D' and len(stack) >= 1:
    stack.append(stack[-1] * 2)

遇到"C"：弹出栈顶元素，要注意判断此时栈中元素个数len(stack)是否大于等于1。

if record == 'C' and len(stack) >= 1:
    stack.pop()

遇到"+"：将栈顶的前两个元素相加后入栈，要注意判断此时栈中元素个数len(stack)是否大于等于2。

if record == '+' and len(stack) >= 2:
    stack.append(stack[-1] + stack[-2])

如果不满足上述的任何一个条件，则说明此时出现异常。应该输出-1。对于可能出现的异常，我们应该在最开始初始化一个标记isError = False，用于标记是否出现异常的标志，初始化为False表示最开始没有异常。当出现异常时，我们修改isError = True，并且break退出循环。

在循环体外，如果isError == True，说明出现了异常，应该直接输出-1，否则输出sum(stack)表示得分总和。

代码

Python

# 题目：2023A-投篮大赛
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问

# 输入表示n个操作的数组ops
ops = input().split(" ")

stack = list()      # 初始化一个空栈，在python中可以用list表示栈
isError = False     # 用于标记是否出现异常的标志，初始化为False表示没有异常

for record in ops:  # 遍历整个ops数组
    # 若record为数字，则直接将该数字加入栈中，注意要将str转为int
    if record != 'D' and record != 'C' and record != '+':
        stack.append(int(record))
    # 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
    elif record == 'D' and len(stack) >= 1:
        stack.append(stack[-1] * 2)
    # 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
    elif record == 'C' and len(stack) >= 1:
        stack.pop()
    # 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值
    elif record == '+' and len(stack) >= 2:
        stack.append(stack[-1] + stack[-2])
    # 如果不满足上述的任何条件，说明出现了异常，
    # 将isError修改为True，同时直接退出循环
    else:
        isError = True
        break

# 如果出现异常，输出-1
# 如果没有异常，输出整个栈中数字的总和
print(-1 if isError else sum(stack))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入表示n个操作的数组ops
        String[] ops = scanner.nextLine().split(" ");

        Stack<Integer> stack = new Stack<>();  // 初始化一个空栈

        boolean isError = false;  // 用于标记是否出现异常的标志，初始化为false表示没有异常

        for (String record : ops) {
            // 若record为数字，则直接将该数字加入栈中，注意要将字符串转为整数
            if (!record.equals("D") && !record.equals("C") && !record.equals("+")) {
                stack.push(Integer.parseInt(record));
            }
            // 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
            else if (record.equals("D") && stack.size() >= 1) {
                stack.push(stack.peek() * 2);
            }
            // 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
            else if (record.equals("C") && stack.size() >= 1) {
                stack.pop();
            }
            // 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值的和
            else if (record.equals("+") && stack.size() >= 2) {
                int top1 = stack.pop();
                int top2 = stack.pop();
                stack.push(top2);
                stack.push(top1);
                stack.push(top1 + top2);
            }
            // 如果不满足上述的任何条件，说明出现了异常
            // 将isError修改为true，同时直接退出循环
            else {
                isError = true;
                break;
            }
        }

        // 如果出现异常，输出-1
        // 如果没有异常，输出整个栈中数字的总和
        int sum = 0;
        if (!isError) {
            while (!stack.isEmpty()) {
                sum += stack.pop();
            }
        }
        System.out.println(isError ? -1 : sum);

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

int main() {
    // 输入表示n个操作的数组ops
    string line;
    getline(cin, line);
    vector<string> ops;
    size_t pos = 0;
    while ((pos = line.find(' ')) != string::npos) {
        ops.push_back(line.substr(0, pos));
        line.erase(0, pos + 1);
    }
    ops.push_back(line);

    stack<int> stack;  // 初始化一个空栈

    bool isError = false;  // 用于标记是否出现异常的标志，初始化为false表示没有异常

    for (const string& record : ops) {
        // 若record为数字，则直接将该数字加入栈中，注意要将字符串转为整数
        if (record != "D" && record != "C" && record != "+") {
            stack.push(stoi(record));
        }
        // 若record为'D'，且栈长度大于等于1，则在栈顶压入两倍的原栈顶值
        else if (record == "D" && stack.size() >= 1) {
            stack.push(stack.top() * 2);
        }
        // 若record为'C'，且栈长度大于等于1，则弹出栈顶元素
        else if (record == "C" && stack.size() >= 1) {
            stack.pop();
        }
        // 若record为'+'，且栈长度大于等于2，则在栈顶压入原栈顶的两个值的和
        else if (record == "+" && stack.size() >= 2) {
            int top1 = stack.top();
            stack.pop();
            int top2 = stack.top();
            stack.push(top1);
            stack.push(top1 + top2);
        }
        // 如果不满足上述的任何条件，说明出现了异常
        // 将isError修改为true，同时直接退出循环
        else {
            isError = true;
            break;
        }
    }

    // 如果出现异常，输出-1
    // 如果没有异常，输出整个栈中数字的总和
    int sum = 0;
    if (!isError) {
        while (!stack.empty()) {
            sum += stack.top();
            stack.pop();
        }
    }
    cout << (isError ? -1 : sum) << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(N)。栈所占用的额外空间。