"🔗 Stack Magic: Minimum Add to Balance Parentheses ⚖️"
\uD83E\uDDE0 Intuition:\n1. "Balancing Parentheses" \uD83E\uDDE9:\n   For every (, we need a matching ).\n    If they don\u2019t match, we need to either remove
# \uD83E\uDDE0 Intuition:\n1. "Balancing Parentheses" \uD83E\uDDE9:\n   <ul><li>For every (, we need a matching ).</li>\n    <li>If they don\u2019t match, we need to either remove extra parentheses or add some.</li></ul>\n\n2. Use a Stack \uD83D\uDDC4\uFE0F:\n    <ul><li>\n    The stack helps us keep track of unmatched parentheses.</li>\n    <li>Push ( when you find one.</li>\n    <li>Pop ( when you find a matching ).</li></ul>\n\n3. Unmatched Parentheses \uD83C\uDFAF:\n    <ul><li>At the end, whatever is left in the stack is the number of unmatched parentheses, which equals how many we need to add to make the string valid.</li>\n</ul>\n\n# \uD83D\uDCA1 Approach:\n1. Start with an empty stack \uD83C\uDD95:\n   <ul><li>stack = ""</li></ul>\n\n2. Traverse the string s \uD83D\uDEB6:\n<ul>\n<li><ul>For each character:\n<li>If the top of the stack is ( and the current character is ), pop the stack (since it\'s a valid pair) \u2796.</li>\n<li>Otherwise, push the current character onto the stack \u2795.</li></ul></li></ul>\n\n3. Final Count \uD83D\uDCCF:\n    <ul><li>The size of the stack at the end gives the number of unmatched parentheses. Return this value.</li><ul>\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n $$O(n)$$\n\n# \uD83D\uDDBC\uFE0F Image Visualization (Stack Operation):\n\n\n   ```\ns = "())("\n\n   Initial Stack: ""\n   Step 1: "("  -> Push  -> Stack: "("\n   Step 2: ")"  -> Pop   -> Stack: ""\n   Step 3: ")"  -> Push  -> Stack: ")"\n   Step 4: "("  -> Push  -> Stack: ")("\n   \n   Final Stack: ")("\n   Unmatched count = 2\n```\n![hfZf8Yf.png](https://assets.leetcode.com/users/images/a0fc08b2-f290-48ae-a0b8-f834aff06689_1728446958.7389562.png)\n\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        string stack="";\n        for(int i=0;i<s.size();i++)\n        {\n            if(stack.size() && stack.back()==\'(\' && s[i]==\')\')\n                stack.pop_back();\n            else\n                stack.push_back(s[i]);\n        }\n\n        return stack.size();\n    }\n};\n```
['String', 'Stack', 'C++']