# Greedy Solution
class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        count_open = 0 
        count_close = 0
        for char in S:
            if char == '(':
                count_open += 1
            if char == ')' and count_open == 0:
                count_close += 1
            if char == ')' and count_open > 0:
                count_open -= 1
        return count_open + count_close



# Stack Solution
class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        stack = []
        count = 0 
        for char in S:
            if char == "(":
                stack.append("(")
            else:
                if stack and stack[-1] == "(":
                    stack.pop()
                else:
                    count += 1
        return count + len(stack)