Baseball Game

🏠 ⬅️ ➡️

You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.

You are given a list of strings operations, where operations[i] is the ith operation you must apply to the record and is one of the following:

  • An integer x.
    • Record a new score of x.
  • '+'.
    • Record a new score that is the sum of the previous two scores.
  • 'D'.
    • Record a new score that is the double of the previous score.
  • 'C'.
    • Invalidate the previous score, removing it from the record.

Return the sum of all the scores on the record after applying all the operations.

The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are valid.

Example 1:

Input: ops = [ "5 ", "2 ", "C ", "D ", "+ "] Output: 30 Explanation: "5 " - Add 5 to the record, record is now [5]. "2 " - Add 2 to the record, record is now [5, 2]. "C " - Invalidate and remove the previous score, record is now [5]. "D " - Add 2 * 5 = 10 to the record, record is now [5, 10]. "+ " - Add 5 + 10 = 15 to the record, record is now [5, 10, 15]. The total sum is 5 + 10 + 15 = 30.

Example 2:

Input: ops = [ "5 ", "-2 ", "4 ", "C ", "D ", "9 ", "+ ", "+ "] Output: 27 Explanation: "5 " - Add 5 to the record, record is now [5]. "-2 " - Add -2 to the record, record is now [5, -2]. "4 " - Add 4 to the record, record is now [5, -2, 4]. "C " - Invalidate and remove the previous score, record is now [5, -2]. "D " - Add 2 * -2 = -4 to the record, record is now [5, -2, -4]. "9 " - Add 9 to the record, record is now [5, -2, -4, 9]. "+ " - Add -4 + 9 = 5 to the record, record is now [5, -2, -4, 9, 5]. "+ " - Add 9 + 5 = 14 to the record, record is now [5, -2, -4, 9, 5, 14]. The total sum is 5 + -2 + -4 + 9 + 5 + 14 = 27.

Example 3:

Input: ops = [ "1 ", "C "] Output: 0 Explanation: "1 " - Add 1 to the record, record is now [1]. "C " - Invalidate and remove the previous score, record is now []. Since the record is empty, the total sum is 0.

Constraints:

  • 1 <= operations.length <= 1000
  • operations[i] is "C ", "D ", "+ ", or a string representing an integer in the range [-3 * 104, 3 * 104].
  • For operation "+ ", there will always be at least two previous scores on the record.
  • For operations "C " and "D ", there will always be at least one previous score on the record.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=100), dimension(:), allocatable :: operations
    integer :: n_ops
    integer :: i
    integer :: result

    call get_args(operations)
    n_ops = size(operations)

    do i = 1, n_ops
        select case (operations(i))
            case ("C")
                ! Invalidates and removes the previous score
                write (*, "(A)") "Invalidating previous score"
            case ("D")
                ! Records a new score that is the double of the previous score
                write (*, "(A)") "Recording double of previous score"
            case ("+")
                ! Records a new score that is the sum of the previous two scores
                write (*, "(A)") "Recording sum of previous two scores"
            case default
                ! Records a new score
                read (operations(i), *) result
                write (*, "(I6)") result
        end select
    end do

contains

    subroutine get_args(operations)
        implicit none
        character(len=100), dimension(:), allocatable, intent(out) :: operations
        integer :: argc
        character(len=100), dimension(:), allocatable :: args
        integer :: i

        call get_command_argument(0, args)
        argc = size(args)

        allocate(operations(argc))

        do i = 1, argc
            operations(i) = args(i)
        end do
    end subroutine get_args

end program main
✅ Compiled
❌ Executed
❌ Correct 
program BaseballScores
    implicit none
    integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
    character(len=1000) :: operations
    integer :: scores(1000)
    integer :: total

    read *, operations

    ! Initialize the scores array with all 0s
    do i = 1, 1000
        scores(i) = 0
    end do

    ! Loop through each operation and apply it to the scores array
    do i = 1, 1000
        select case(operations(i:i+1))
            case('+ ')
                scores(i+1) = scores(i) + scores(i-1)
            case('D ')
                scores(i+1) = scores(i) * 2
            case('C ')
                scores(i) = 0
            case default
                read(operations(i:i+1),*) scores(i+1)
        end select
    end do

    ! Calculate the total sum of all scores
    total = 0
    do i = 1, 1000
        total = total + scores(i)
    end do

    ! Output the total sum
    write (*,*) total
end program BaseballScores
🌐 Data from online sources 
def calPoints(ops):
    record = []
    for op in ops:
        if op == '+':
            record.append(record[-1] + record[-2])
        elif op == 'D':
            record.append(record[-1] * 2)
        elif op == 'C':
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

We use a dynamic array (in languages other than Java, where we use LinkedList for simplicity) to store the valid scores. We iterate through the given `ops` array of strings, and for each string, we perform the operations as follows:
  1. If the operation is '+', we add the last two scores and append the sum to the record.
  2. If the operation is 'D', we double the last score and append it to the record.
  3. If the operation is 'C', we remove the last score from the record.
  4. If the operation is a number, we parse the integer value and append it to the record.

After iterating through all operations, we calculate the sum of all the scores in the record and return it.

The time complexity of this algorithm is O(n) where n is the size of ops, as we iterate once through the array and perform constant-time operations within the loop. The space complexity is also O(n), as we store the valid scores in the record array.

🌐 Data from online sources 
#include <vector>
#include <string>

int calPoints(std::vector<std::string>& ops) {
    std::vector<int> record;
    for (const std::string& op : ops) {
        if (op == "+") {
            record.push_back(record[record.size() - 1] + record[record.size() - 2]);
        } else if (op == "D") {
            record.push_back(2 * record.back());
        } else if (op == "C") {
            record.pop_back();
        } else {
            record.push_back(stoi(op));
        }
    }
    return std::accumulate(record.begin(), record.end(), 0);
}

We use a dynamic array (in languages other than Java, where we use LinkedList for simplicity) to store the valid scores. We iterate through the given `ops` array of strings, and for each string, we perform the operations as follows:
  1. If the operation is '+', we add the last two scores and append the sum to the record.
  2. If the operation is 'D', we double the last score and append it to the record.
  3. If the operation is 'C', we remove the last score from the record.
  4. If the operation is a number, we parse the integer value and append it to the record.

After iterating through all operations, we calculate the sum of all the scores in the record and return it.

The time complexity of this algorithm is O(n) where n is the size of ops, as we iterate once through the array and perform constant-time operations within the loop. The space complexity is also O(n), as we store the valid scores in the record array.