首先我们先了解一下这一道水题:
【问题描述】
给你一个只有小括号和中括号和大括号的括号序列,问该序列是否合法。
【输入格式】
一行一个括号序列。
【输出格式】
如果合法,输出OK,否则输出Wrong。
【样例输入】
[(])
【样例输出】
Wrong
【数据范围与规定】
对于的数据,序列长度不超过1000。
解析:
关于这种括号匹配的题,首先要想到的是通过 stack 来进行做,而关于 stack 本博客之前讲过,这道题便可以说是 stack 的一个模板题...这里介绍两种做法...
方法一: 用数组进行模拟栈,自己做一个手动栈,时间上可能会比 STL库中提供的栈会快一些...
1 #include<cstdio> 2 #include<cstring> 3 4 using namespace std; 5 6 char s[1005], z[1005]; 7 8 int size; 9 10 int main(){11 scanf("%s",s);12 int l = strlen(s);13 size++;14 z[size] = s[1];15 for (int i = 2; i <= l; i++){16 if (s[i] == ')'){17 if (z[size] != '('){18 printf("Wrongn");19 return 0;20 }21 else size--;22 }23 if (s[i] == ']'){24 if (z[size] != '['){25 printf("Wrongn");26 return 0;27 }28 else size--;29 }30 if (s[i] == '}'){31 if (z[size] != '{'){32 printf("Wrongn");33 return 0;34 }35 else size--;36 }37 if (s[i] == '{' || s[i] == '[' || s[i] == '('){38 size++;39 z[size] = s[i];40 }41 }42 if(size != 0) printf("Wrongn");43 else printf("OKn");44 45 return 0;46 } stack by hand
方法二: 直接用STL中的栈:
1 #include<cstdio> 2 #include<cstring> 3 #include<stack> 4 5 using namespace std; 6 7 char s[1005]; 8 int l; 9 10 stack <int> k;11 12 int main(){13 scanf("%s",s);14 l = strlen(s);15 k.push(s[1]);16 for (int i = 2; i <= l; i++){17 if (s[i] == ')'){18 if (k.top() != '('){19 printf("Wrongn");20 return 0;21 }22 else k.pop();23 }24 if (s[i] == ']'){25 if (k.top() != '['){26 printf("Wrongn");27 return 0;28 }29 else k.pop();30 }31 if (s[i] == '}'){32 if (k.top() != '{'){33 printf("Wrongn");34 return 0;35 }36 else k.pop();37 }38 if (s[i] == '(' || s[i] == '{' || s[i] == '['){39 k.push(s[i]);40 }41 }42 if (!k.empty()) printf("Wrongn");43 else printf("OKn");44 return 0;45 } stack by STL
关于括号问题——一般都是关于栈的模板
转载于:https://www.cnblogs.com/New-ljx/p/10415551.html