专栏文章

题解：P14172 【MX-X23-T2】括号串

MMilkyWayjzn
P14172题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minof91m
此快照首次捕获于
2025/12/02 05:43
3 个月前
此快照最后确认于
2025/12/02 05:43
3 个月前
查看原文

P14172题解

思路

开两个栈，一个栈 s1s1 存储左括号的位置，另一个栈 s2s2 存储右括号的位置。
当遍历所有括号时，如果遇到左括号且 s2s2 栈顶的值等于该位置减一，则说明 “)(” 可以变成“()”，然后弹出 s2s2 栈顶，用一个变量 cntcnt（记录变化次数） 加一。但如果 s2s2 栈顶的值不等于当前位置减一或为空，则将该左括号的位置压入栈 s1s1 中。
当遍历所有括号时，如果遇到右括号且该位置之前有未匹配的左括号，则将 s1s1 栈顶弹出。但如 s1s1 为空，则将该右括号的位置 压入栈s2s2 中。
最后，如果两个栈为空，且 cntcnt 小于或等于一（因为最多只能变换一次），则输出 Yes 。否则输出 No 。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	stack<int> s1,s2;//分别存储左括号和右括号的位置 
	while(t--){
		while(!s1.empty()) s1.pop();//清空 
		while(!s2.empty()) s2.pop();
		int n;
		cin>>n;
		int cnt=0;//变换次数计数器 
		for(int i=1;i<=n;i++){
			char x;
			cin>>x;
			if(x=='('){
				if(!s2.empty()&&s2.top()+1==i){//栈s2顶部的值加一等于该位置 
					s2.pop();//弹出 
					cnt++;//计数器加一 
				} 
				else s1.push(i);//否则，直接压入栈s1 
			} 
			else{
				if(!s1.empty()) s1.pop();//只要栈s1不为空，则可以匹配 
				else s2.push(i);//如果为空，将右括号位置压入栈s2 
			}
		}
		if(s1.size()||s2.size()||cnt>1) cout<<"No"<<endl;//只要两个栈内还有东西，就不能 
		else cout<<"Yes"<<endl;
	}
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...