题目传送门

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

切入正题:

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

载入天数...载入时分秒...