本文主要是介绍COJ 1065括号匹配:栈的简单应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
[STL]【数据结构】括号匹配
Time Limit: 1000 ms Memory Limit: 65536 KBTotal Submit: 43 Accepted: 11
Description
数据有一行,由(,),[,],{,}六种字符构成。现在判断这行括号是否合法,合法条件如下:
1、每个左括号都有对应的右括号匹配,不得有多余的括号,比如这样正确:{}(),但这样错误:()())
2、不同类型括号之间不可以交错,比如这样正确:{[]},但这样错误:{[}]
1、每个左括号都有对应的右括号匹配,不得有多余的括号,比如这样正确:{}(),但这样错误:()())
2、不同类型括号之间不可以交错,比如这样正确:{[]},但这样错误:{[}]
Input
一行,只有六种括号字符
Output
括号合法输出:YES
括号不合法输出:NO
括号不合法输出:NO
Sample Input
Sample Input 1:
{}{}{}()(){[]}
Sample Input 2:
{}[]]{[})())
{}{}{}()(){[]}
Sample Input 2:
{}[]]{[})())
Sample Output
Sample Output 1:
YES
Sample Output 2:
NO
YES
Sample Output 2:
NO
Hint
栈
如采用逐个字符输入时,建议使用getchar();
<stack>
如采用逐个字符输入时,建议使用getchar();
<stack>
思路:被getchar一直TLE,后面改用字符串输入就得过了,真是很无语有木有!!!暗示居然还是个陷阱……唉……中间也没看好题目,理解错了又错了几次,刚开始还以为{[}]这样也属于匹配的,后面重新看题目了才知道理解错了,一直纠结这事……
#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
int cmp(char a,char b)
{if(a=='{'&&b=='}') return 1;if(a=='('&&b==')') return 1;if(a=='['&&b==']') return 1;return 0;
}
int main()
{stack<char>s;char c[101];int i,l;scanf("%s",c);l=strlen(c);for(i=0;i<l;i++){if(!s.empty()&&cmp(s.top(),c[i]))s.pop();else s.push(c[i]);}if(!s.empty()) printf("NO\n");else printf("YES\n");return 0;
}
这篇关于COJ 1065括号匹配:栈的简单应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!