C++ || Easy Stack Approach✅✅
Intuition\nThe goal is to determine how many parentheses must be added to make a given string valid. A valid parentheses string is one where every opening paren
# Intuition\nThe goal is to determine how many parentheses must be added to make a given string valid. A valid parentheses string is one where every opening parenthesis `\'(\'` has a corresponding closing parenthesis `\')\'`. \n\nTo achieve this, we can use a stack to track unmatched opening parentheses and a counter to count unmatched closing parentheses.\n\n# Approach\n- Traverse through the string character by character.\n- If we encounter an opening parenthesis `\'(\'`, push it onto the stack.\n- If we encounter a closing parenthesis `\')\'`:\n  - If the stack is empty, increment a counter `maxi` as it indicates an unmatched closing parenthesis.\n  - If the stack is not empty and the top of the stack is an opening parenthesis `\'(\'`, we pop the stack to balance it.\n- Finally, the number of unmatched opening parentheses will be the size of the stack, and the number of unmatched closing parentheses will be stored in `maxi`. The total number of additions needed is the sum of these two values.\n\n# Complexity\n- **Time complexity:** O(n)\n- **Space complexity:** O(n)\n\n# Code\n\n```\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int maxi = 0;\n        stack<char> st;\n        for(int i=0; i<s.length(); i++){\n            if(s[i] == \')\' && st.empty()){\n                maxi++;\n            }\n            else if(s[i] == \')\' && st.top() == \'(\') st.pop();\n            else st.push(s[i]);\n        }\n        return st.size()+maxi;\n    }\n};\n```
['Stack', 'C++']