题目传送门

明显，这是一道用栈解决的水题。但是除了栈，还有另外一种简单一点的方法。

切入正题：

1.栈(stack)

运用STL中的#include<stack>

stack<类型> st;
压栈 st.push(元素);
出栈 st.pop();
获取栈顶元素 st.top();
栈的大小(元素个数) st.size();
判断栈是否为空(栈空输出true，反之亦然) st.empty();

例：判断括号是否匹配

bool check(string s)
{
    stack<char> st;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='(') st.push(s[i]); //左括号进栈
        else{ //不是左括号就是右括号
            if(st.empty()) return 0; //如果当前栈空，莫名其妙来一个右括号即为不匹配
            else st.pop(); //说明栈里有待匹配的左括号，弹出一个（配对成功）
        }
    }
    return 1;
}

上代码

真是喜闻乐见的一个环节呢

int ans=0;
string s;
stack<char> st;
int main()
{
    cin>>s;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='(') st.push(s[i]); //左括号进栈
        else{ //不是左括号就是右括号
            if(st.empty()){st.push('('); ans++;} //注意。如果不匹配就说明需要括号反转，因此反转括号，ans++
            else st.pop();
        }
    }
    if(!st.empty()) ans+=st.size()/2; //如果剩下一堆左括号，说明需要反转一半的才能配对成功
    cout<<ans<<endl;
    return 0;
}

2.加减计数法

和栈的原理差不多，只不过简单易懂，不用掌握栈。时间的话让我们大声喊出：STL NB!

左括号+1，右括号-1。如果匹配的话就是0了。

当然也有反例：())(单纯判断最终结果是否为0会出错WA

因此，我们可以发现：如果当前为0(栈空)再加入一个右括号那就需要反转了

string s;
int ans=0,p=0;
int main()
{
    cin>>s;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='(') p++; //类似进栈
        else{ //不是左括号就是右括号
            if(p) p--; //有一个左括号等待配对，那就配对
            else ans++,p++; //反转
        }
    }
    ans+=p/2; //道理同栈
    cout<<ans<<endl;
    return 0;
}

结尾小声bb：感觉题目背景尽是扯淡2333


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议


 上一页

music