括号表达式匹配的条件：从左往右，左括号个数大于等于右括号个数，且最后左右括号数相等。

LC 921. 使括号有效的最少添加

题目：添加最少数目的左括号或右括号，使得表达式有效
方法：
贪心，遇到右括号，能匹配就匹配，不能匹配就答案加1。
为什么这是最少的次数就不会证明了...

class Solution {
public:
    int minAddToMakeValid(string s) {
        int left = 0, ans = 0;
        for(char ch : s) {
            if(ch == '(')  left++;
            else {
                if(left == 0)  ans++;
                else left--;
            }
        }
        return ans+left;
    }
};

LC 1963. 使字符串平衡的最小交换次数

题目：字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。返回使 s 变成 平衡字符串 所需要的 最小 交换次数。
方法：
贪心。从前往后，能匹配就匹配，不能匹配就交换。
不会证明正确性。

class Solution {
public:
    int minSwaps(string s) {
        int i = 0, j = s.size()-1;
        int cnt = 0, ans = 0;
        for(char ch : s) {
            if(ch == '[')  cnt++;
            else {
                if(cnt == 0) {ans++; cnt++;}
                else cnt--;
            }
        }
        return ans;
    }
};

LC 301. 删除无效的括号

题目：删除最小数量的无效括号，使得输入的字符串有效。要求返回所有可能的结果。
方法：
看似是921的翻版，但方法完全不一样。
看这条件 1 <= s.length <= 25，暴搜无疑了。
BFS：给定一个表达式，删除一个元素得到拓展表达式。

class Solution {
public:
    bool check(const string& s) {
        int left = 0;
        for(char ch : s) {
            if(ch == '(')  left++;
            if(ch == ')')  left--;
            if(left < 0)  return false;
        }
        return left==0;
    }
    vector<string> removeInvalidParentheses(string s) { 
        bool flag = false;
        vector<string>res;
        queue<string>q;
        unordered_set<string>vis;
        q.push(s);
        vis.insert(s);
        while(!q.empty()) { // BFS
            cout << "size: " << q.size() << endl;
            int size = q.size();
            for(int i = 0;i < size;i++) {  // 层次遍历
                string s = q.front();q.pop();
                cout << s << endl;
                if(check(s)) { 
                    res.push_back(s);
                    flag = true;
                }
                if(flag)  continue;  // 如果已经找到，都不用扩展了
                for(int j = 0;j < s.size();j++) {
                    if(s[j] != '(' && s[j] != ')')  continue;
                    string new_s = s.substr(0, j) + s.substr(j+1);
                    if(!vis.count(new_s)) {
                        vis.insert(new_s);
                        q.push(new_s);
                    }
                }
            }
            if(flag)  break;  // 本轮已经找到了
        }
        return res;
    }
};

LC 1249. 移除无效的括号

题目：从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。请返回任意一个合法字符串。
方法：
与上一题相比，只需要返回任意一个。
和添加一样，可以贪心得到。参考 2种解法,简洁代码,秒懂详解--[1249]

方法一：栈（由内向外）

把左括号入栈，右括号取栈顶匹配，所以是从内向外匹配。

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        vector<int>removing;   // 当做栈
        for(int i = 0;i < s.size();i++) {
           if(s[i] == '(')  removing.push_back(i);  // 记录左括号的位置
           if(s[i] == ')') {
               if(removing.size() > 0) removing.pop_back();
               else s[i] = '*';
           }
        }
        for(int idx : removing)  s[idx] = '*';
        s.erase(remove(s.begin(), s.end(), '*'), s.end());
        return s;
    }
};

方法二：计数（由外向内）

先统计右括号个数。再前往后遍历，遇到左括号尝试匹配，遇到右括号也先尝试匹配。

class Solution {
public:
    string minRemoveToMakeValid(string s) {
       int left = 0, right = count(s.begin(), s.end(), ')');
       string res = "";
       for(char& ch : s) {
           if(ch == '(') {
               if(right > 0) {   // 如果有右括号，就一定能匹配
                   left++;
                   right--;
                   res += ch;
               }
           }
           else if(ch == ')') {
               if(left > 0) {  // 匹配掉一个
                    left--;
                    res += ch;
               } 
               else right--;  // 删除右括号，当前右括号太多了
           }
           else res += ch;
       }
       return res;
    }
};