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:
x
.
x
.'+'
.
'D'
.
'C'
.
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]
."+"
, there will always be at least two previous scores on the record."C"
and "D"
, there will always be at least one previous score on the record.This problem simulates a baseball game's scoring system using a stack data structure. The goal is to calculate the total score after applying a series of operations.
Approach:
The solution uses a stack to store the scores. Each operation is processed sequentially:
Integer: If the operation is an integer (e.g., "5", "-2"), it's pushed onto the stack.
'+': If the operation is "+", the sum of the top two elements on the stack is calculated and pushed onto the stack. This represents adding the scores of the previous two plays. We must ensure the stack contains at least two elements before performing this operation.
'D': If the operation is "D", the top element is doubled and pushed onto the stack. This means doubling the score of the previous play. Again, we need to verify the stack is not empty.
'C': If the operation is "C", the top element is popped from the stack. This invalidates the last recorded score. The stack should contain at least one element for this operation.
Finally, the sum of all elements remaining in the stack is calculated and returned as the total score.
Time Complexity: O(n), where n is the number of operations. Each operation takes constant time O(1) on average, and we iterate through all n operations.
Space Complexity: O(n) in the worst case. The stack can grow up to the size of the number of operations if we continuously add scores without any 'C' operations.
Code Examples (with detailed comments):
Python:
def calPoints(operations):
"""
Calculates the total score of a baseball game.
Args:
operations: A list of strings representing the operations.
Returns:
The total score after applying all operations.
"""
stack = [] # Initialize an empty stack to store scores
for op in operations:
if op.isdigit() or (op.startswith('-') and op[1:].isdigit()): #check if it's an integer
stack.append(int(op)) # Push integer onto the stack
elif op == '+':
if len(stack) >= 2: # Check for sufficient elements
stack.append(stack[-1] + stack[-2]) # Add top two elements and push result
else:
raise ValueError("Not enough elements in the stack for '+' operation.")
elif op == 'D':
if stack: #Check if stack is not empty
stack.append(stack[-1] * 2) # Double the top element and push result
else:
raise ValueError("Stack is empty. Cannot perform 'D' operation.")
elif op == 'C':
if stack: # Check for elements to pop
stack.pop() #remove the last element
else:
raise ValueError("Stack is empty. Cannot perform 'C' operation.")
else:
raise ValueError("Invalid operation: " + op) #Handle Invalid operations
return sum(stack) #return the sum of all remaining elements in stack
Java:
import java.util.Stack;
class Solution {
public int calPoints(String[] operations) {
Stack<Integer> stack = new Stack<>();
for (String op : operations) {
if (op.matches("-?\\d+")) { // Check if it's an integer (positive or negative)
stack.push(Integer.parseInt(op));
} else if (op.equals("+")) {
if (stack.size() >= 2) {
int second = stack.pop();
int first = stack.peek();
stack.push(second);
stack.push(first + second);
} else {
throw new IllegalArgumentException("Not enough elements for '+'");
}
} else if (op.equals("D")) {
if (!stack.isEmpty()) {
stack.push(stack.peek() * 2);
} else {
throw new IllegalArgumentException("Stack is empty for 'D'");
}
} else if (op.equals("C")) {
if (!stack.isEmpty()) {
stack.pop();
} else {
throw new IllegalArgumentException("Stack is empty for 'C'");
}
} else {
throw new IllegalArgumentException("Invalid operation: " + op);
}
}
int totalScore = 0;
for (int score : stack) {
totalScore += score;
}
return totalScore;
}
}
Other languages (C++, Javascript, Go, etc.) would follow a similar structure, utilizing their respective stack implementations and handling integer parsing and error conditions appropriately. Remember to include error handling to deal with invalid inputs as shown in the examples.