Minimum Add to Make Parentheses Valid

给一个string, 里面是括号, 求最少添加几个括号, 让string valid.

用stack跟踪string的左括号. 最后stack的大小就是答案

class Solution {
public:
    int minAddToMakeValid(string S) {
        stack<char> st; 
        for(auto c : S) {
            if(c == '('){
                st.push(c);
            }else{
                if(st.empty()){
                    st.push(c);
                }else{
                    if(st.top() == '('){
                        st.pop();
                    }
                    else{
                        st.push(c);
                    }
                }
            }
        }
        return st.size();
    }
};