LeetCode 921. 使括号有效的最少添加（栈）

示例 1：
输入："())"
输出：1

示例 2：
输入："((("
输出：3

示例 3：
输入："()"
输出：0

示例 4：
输入："()))(("
输出：4
 
提示：
S.length <= 1000
S 只包含 '(' 和 ')' 字符。

class Solution {
public:
    int minAddToMakeValid(string S) {
        stack<char> stk;
        for(int i = 0; i < S.size(); ++i)
        {
        	if(stk.empty())
        		stk.push(S[i]);
        	else
        	{
        		if(stk.top()=='(' && S[i]==')')
        			stk.pop();
        		else
        			stk.push(S[i]);
        	}
        }
        return stk.size();//未匹配的字符数
    }
};

class Solution {
public:
    int minAddToMakeValid(string S) {
        int left = 0;
        int right = 0;
        for(char &c:S)
        {
            if(c=='(') 
                left++;
            else
            {
                if(left>0) //右括号可以与之匹配
                    left--;
                else //右括号没有相应的左括号匹配
                    right++;
            }   
        }
        return left+right;
    }
};