A parentheses string is valid if and only if:


	It is the empty string,
	It can be written as AB (A concatenated with B), where A and B are valid strings, or
	It can be written as (A), where A is a valid string.


You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.


	For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".


Return the minimum number of moves required to make s valid.

&nbsp;
Example 1:

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


Example 2:

Input: s = "((("
Output: 3


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 1000
	s[i] is either '(' or ')'.


class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []

        for parenthese in s:
            if parenthese == "(":
                stack.append("(")

            else:
                if not stack or stack[-1] == ")":
                    stack.append(")")

                if stack and stack[-1] == "(":
                    stack.pop()

        return len(stack)
class Solution {
    public int minAddToMakeValid(String s) {
        int open = 0;
        int extra = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                open++;
            }else{
                if(open==0){
                    extra++;
                }else{
                    open--;
                }
            }
        }
        return open+extra;
    }
}
class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> sta;
        int nums = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(')
            {
                sta.push(s[i]);
            }
            else
            {
                if (!sta.empty())
                {
                    sta.pop();
                }
                else
                {
                    nums++;
                }
            }
        }
        nums += sta.size();
        return nums;
    }
};
var minAddToMakeValid = function(s) {
    let stack = []
    let count = 0
    for(let i=0;i<s.length;i++) {
        let ch = s[i]
        if(ch === '(') {
            stack.push(ch)
        } else {
            let top = stack.pop()
            if(top != '(') count++
        }
    }

    count += stack.length

    return count
};
Minimum Add to Make Parentheses Valid