括号匹配
匹配 括号
2023-09-14 09:08:54 时间
问题描述
蒜头君在纸上写了一个串,只包含’(‘和’)’。一个’(‘能唯一匹配一个’)’,但是一个匹配的’(‘必须出现在’)’之前。请判断蒜头君写的字符串能否括号完全匹配,如果能,输出配对的括号的位置(匹配的括号不可以交叉,只能嵌套)。
输入格式
一行输入一个字符串只含有’(‘和’)’,输入的字符串长度不大于50000。
输出格式
如果输入括号不能匹配,输出一行”No”,否则输出一行”Yes”,接下里若干行每行输出 2 个整数,用空格隔开,表示所有匹配对的括号的位置(下标从 1 开始)。你可以按照任意顺序输出。
本题答案不唯一,符合要求的答案均正确
样例输入
()()
样例输出
Yes
1 2
3 4
1 #include<iostream>
2 #include<stack>
3 using namespace std;
4 struct record{
5 char c;
6 int i;//方便记录下标,但是容易浪费空间
7 };
8 int arr[25000][2],t=0;
9 char str[50000];
10 stack<record> st;
11 int main(){
12 char ch;
13 int i=0;
14 gets(str);
15 while (str[i])
16 {
17 if (str[i]=='('){
18 //stack中只保存(,节省空间
19 record obj;
20 obj.c=str[i];
21 obj.i=i+1;
22 st.push(obj);
23 }
24 //找到第一个) ,对其进行处理,判断stack里面是否有可以匹配的(,若无,则stack为空,不满足条件
25 if (str[i]==')')
26 {
27 if (st.empty())
28 {
29 //数据 (())))))
30 cout<<"No";
31 return 0;
32 }
33 arr[t][0]=st.top().i;//取栈顶元素,获得标号
34 arr[t++][1]=i+1;
35 // cout<<arr[t-1][0]<<" "<<arr[t-1][1]<<endl;
36 st.pop();//弹出栈顶元素
37 }
38 i++;
39 }
40 if (st.empty())
41 {
42 //数据 (((())))
43 cout<<"Yes"<<endl;
44 for (int j = 0; j < t; j++)
45 {
46 cout<<arr[j][0]<<" "<<arr[j][1]<<endl;
47 }
48 }else
49 {
50 // 数据 (()
51 cout<<"No"<<endl;
52 }
53 }
相关文章
- 括号匹配
- Java实现 蓝桥杯 算法提高 字符串匹配
- java实现括号的匹配
- java实现括号的匹配
- Nginx、PCRE和中文URL(UTF8编码)rewrite路径重写匹配问题
- Scala模式匹配:对列表进行匹配
- redisTemplate使用scan模糊匹配key
- 华为OD机试 - 括号匹配(Java & JS & Python)
- 人脸匹配搜索指北
- 【华为机试真题 Python实现】括号匹配II
- 集群服务器查找确定自己所属队列 如何匹配所有230218989字符出现的地方及其之后50行: bqueues -l |grep 230238989
- 匹配第一个括号里的内容 r
- Java如何找到一个单词的每一次匹配?
- 【三】3D匹配Matching之可变形曲面匹配Deformable Surface—read_deformable_surface_model()算子
- 【三】3D匹配Matching之外形匹配Shape—Based——serialize_shape_model_3d()/ trans_pose_shape_model_3d()算子
- (C语言)检测括号是否匹配