Minimum Add to Make Parentheses Valid

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Example:

Input:  str="())"
Output: 1

Approach

Java

public class MinAddMakeParenthesesValid {
    public static void main(String[] args) {
        String str = "())";
        System.out.println(minAddToMakeValid(str));
    }

    // function to find the number
    // of add to make string valid
    static int minAddToMakeValid(String s) {
        int cnt = 0;
        int n = s.length();
        int open = 0;

        // iterate till the length of string
        for (int i = 0; i < n; i++) {

            // if open bracket push into
            // the stack
            if (s.charAt(i) == '(')
                open++;

            // if closing bracket
            else if (s.charAt(i) == ')') {
                if (open == 0)
                    cnt++;
                else
                    open--;
            }

        }
        cnt = cnt + open;
        // return the count
        return cnt;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the number
//of add to make string valid
int minAddToMakeValid(string s) 
{
    stack<char> st;
    int cnt=0;
    int  n=s.size();

    //iterate till the length of string
    for(int i=0;i<n;i++)
        {

            //if open bracket push into
            //the stack
            if(s[i]=='(')
                  st.push(s[i]);

            //if closing bracket
            else if(s[i]==')')
            {

                //if stack is empty increment
                //the count
                if(st.empty())
                      cnt++;

                //else pop from the stack
                else
                    st.pop();
            }
                
        }
   //uodate the count   
   cnt+=st.size();

   //return the count 
    return cnt;
}
int main()
{
    string str="())";
    cout<<minAddToMakeValid(str);
    return 0;
}