O(n) 100% python solution with step by step explanation
IntuitionWe will solve this problem using stacks because we have to do operations to the last index like popping or doubling or sum of the previous two indexes.
# Intuition
We will solve this problem using stacks because we have to do operations to the last index like popping or doubling or sum of the previous two indexes.

# Approach
So, we will create an empty stack which will store our output. We will write a for loop which cover all the scenarios like:
-> '+' means we have to add the sum of the previous two elemts which can be done by taking -1 and -2 values of the stack which are last and second last respectively.

-> 'D' means we have to double the previous elemt which can be done by taking the last value ie -1 of the stack and multiplying it by 2.

-> 'C' means we have to invalidate the previous index meaning pop it from the stack which can be done by using stack.pop() func.

-> last being int, meaning a new int is added to the end of the stack which can be done by appending it to the stack of operations.

Upon looping, we will return the sum of the stack as output.

# Example of the operation:
-> ops = ["5","-2","4","C","D","9","+","+"]
This is the input array we're given. Now, we will begin performing the operations.
First, we have 5 so we will add it to the stack which we're going to return as sum.
-> stack = [5]

Next is -2, so we add it to the stack and same for the next elemt ie 4.
-> stack = [5, -2, 4]

Now, we encounter a 'C' which means we have to invalidate the previous index ie on top from the stack.
-> current stack = [5, -2, 4]
Upon performing 'C':
-> stack = [5, -2]

Now, we encounter a 'D' which means we have to double the last index by * 2:
-> stack = [5, -2, -4]

Now, we have a 9. So, we add it to the stack.
-> stack = [5, -2, -4, 9]

Now, we have to perform a '+' operation which we have to calculate the sum of previous two indexes and added it to the stack as new elmt:

-> + = -4 + 9 = 5
-> stack = [5, -2, -4, 9, 5]

Now, we again perform a '+' operation on 9 and 5 and append it to the stack:
-> + = 9 + 5 = 14
-> stack = [5, -2, -4, 9, 5, 14]

Now, we have performed all the operations. We calculate the sum of the stack:

-> stack = [5, -2, -4, 9, 5, 14]
-> 5 + (-2) + (-4) + 9 + 5 + 14
-> 3 + (-4) + 9 + 5 + 14
-> (-1) + 9 + 5 + 14
-> 8 + 19
-> 27

The sum of the stack is 27 which will be our output.

![Screenshot 2025-02-20 at 9.01.47 PM.png](https://assets.leetcode.com/users/images/4b2c719f-850e-4050-bb7a-d8f76af95b43_1740065543.2139046.png)

# Complexity
- Time complexity:
O(n) where n denotes the number of elemts and as we're looping through the operations and appending and popping from the stack is done to the last index. So, doing that on a dynamic array is a constant thing to do.

- Space complexity:
O(n) because the length of the stack depends on the number of elmts we add to the stack like adding all integers and not performing any operations on it.

# Code
```python3 []
class Solution:
    def calPoints(self, operations: List[str]) -> int:
        stack = [] #empty stack

        for op in operations:
            if op == '+': # + which means adding previous two elemts -1 means last and -2 means second last
                stack.append(stack[-1] + stack[-2])
            elif op == 'D': # D means double the score which means -1 which last elemt multiplied by 2
                stack.append(stack[-1] * 2)
            elif op == 'C': # C means invalidate the last score means we pop it from the stack
                stack.pop()
            else: # it's an integer so we append it to the stack
                stack.append(int(op)) 

        return sum(stack) # we return the sum of the stack as output

```
['Python3']