class Solution {
public:
    int minAddToMakeValid(string S) {
        stack <char> stk;
        
        for (auto s:S)
        {
            if (s==')' && stk.top() == '(')
            {
                stk.pop();
            }
            else 
            {
                stk.push(s);
            }
            
         }
        int size = 0;
        while (!stk.empty())
        {
            size++;
            stk.pop();
        }
        return size;
    }
};