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

Formally, a parentheses string is valid if and only if:

• It is the empty string, or
• It can be written asAB(Aconcatenated withB), whereAandBare valid strings, or
• It can be written as(A), whereAis a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

每当右括号比左括号多的时候，就需要补全，并记得重置左右括号个数。到最后再补全可能缺少的右括号

class Solution {
    public int minAddToMakeValid(String S) {
        if(S == null || S.length() == 0)
            return 0;

        int left = 0;
        int right = 0;
        int len = S.length();
        int res = 0;

        for(int i = 0; i < S.length(); i++) {
            if(S.charAt(i) == '(') {
                left++;
            } else {
                right++;
                if(right > left) {
                    res += right - left;
                    left = 0;
                    right = 0;
                }
            }
        }

        res += Math.abs(left - right);
        return res;
    }
}