[C++知识库]括号匹配 计蒜客 - 42574

括号匹配 计蒜客 - 42574

问题描述

蒜头君在纸上写了一个串，只包含’(‘和’)‘。
一个’(‘能唯一匹配一个’)‘，但是一个匹配的’(‘必须出现在’)'之前。
请判断蒜头君写的字符串能否括号完全匹配，
如果能，输出配对的括号的位置（匹配的括号不可以交叉，只能嵌套）。

输入格式
一行输入一个字符串只含有’(‘和’)'，输入的字符串长度不大于 50000。

输出格式
如果输入括号不能匹配，输出一行"No"，否则输出一行"Yes"，
接下里若干行每行输出 2 个整数，用空格隔开，表示所有匹配对的括号的位置（下标从 1 开始）。
你可以按照任意顺序输出。

样例输入

(())

样例输出

Yes
1 4
2 3

• 参考程序

#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
using namespace std;
const int N=1e5+10;
int a[N], b[N], cnt=0;
stack<int> sta;
int main(){
//    freopen("data.in","r",stdin);
    string s; getline(cin, s);
    bool flag=1;
	for(int i=0; i<s.length(); i++){
		if(s[i]=='(') sta.push(i);
		else if(s[i]==')') {
			if(!sta.empty()) {
				++cnt;
				a[cnt] = sta.top()+1;
				b[cnt] = i+1;
				sta.pop();
			} else {
				flag=0; break;
			}
		}
	}
	if(flag && sta.empty()) {
		cout<<"Yes"<<endl;
		for(int i=1; i<=s.length()/2; i++){
			cout<<a[i]<<" "<<b[i]<<endl;
		}
	}else cout<<"No"<<endl;
    return 0;
}