1249移除无效的括号

下面是题目

我的思路（挺慢的）

我的思路是写两个栈，一个存储字符串，一个进行判断左右括号，和众多的括号题一样，我选择左括号进栈，匹配到右括号两栈皆pop，形成新的字符串,具体在代码中解释

class Solution {
public:
string minRemoveToMakeValid(string s) {
        stack<int>k;
        stack<string>stack;
        string res;
    	//遍历字符串s
        for(auto c:s)
        {
            //如果存储括号的栈为空，但是有一个右括号，肯定不合法的
            if(k.empty()&&c==')')
                continue;
            //如果是字母的话，把它加到res中去
            if(isalpha(c))
                res+=c;
            //如果是左括号，把res入栈后置0
            else if(c=='(')
            {
                stack.push(res);
                k.push(0);
                res = "";
            }
    //如果是右括号，这时候栈非空说明匹配上了，那么就用存储字符串的栈顶+(res),形成新的res
            else if(c==')')
            {
                res = stack.top()+'('+res+')';
                stack.pop();
                k.pop();
            }
        }
//遍历完成后，如果stack非空，那么要把stack中的内容加到res前面，因为可能存在很多左括号"()(()(("
        while (!stack.empty())
        {
            res = stack.top()+ res;
            stack.pop();
        }
    return  res;
    }
};

但是还有更好的思路！！！

就是先判断哪些位置的括号是无效的，然后通过移除、置0再判断等方法进行消除即可

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> str1;
        //首先判断那些括号，是无效的，记录他们的位置
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(')
            {
                str1.push(i);
            }
            if(s[i]==')')
            {
                if(str1.empty()||s[str1.top()]==')')   str1.push(i);
                else str1.pop();
            }
        }
        //用erase的方法，定点移除s中第(str1.top())位的一个元素，也就是那个无效的括号
        for(int i=0;!str1.empty();i++)
        {
            s.erase(str1.top(),1);
            str1.pop();
        }
        return s;
    }
};