首页 > 代码库 > 平衡的括号Uva-673
平衡的括号Uva-673
题意大概:输入一个包括“()”和“[ ]”的括号序列,判断是否合法。具体规则如下:
1.空串合法。
2.如果A和B都合法,那么AB也合法。
3.如果A合法,那么[A]和(A)都合法。
思路:
初始化一个栈,输入序列,然后进行扫描:
1.序列长度肯定是偶数(包括 0);
2.如果是“[”或者“(”则将其压进栈里面;
3.如果是“)”或者“]”,则根据当前栈顶的元素值进行判断,
如果匹配不成功的话,就不用再进行匹配了,肯定是不能成功的!
代码如下:
<span style="font-family:KaiTi_GB2312;font-size:18px;"><strong>#include<cstdio> #include<iostream> #include<cstring> #include<stack> using namespace std; const int maxn=201314; char str[maxn]; stack<char> s;//用来存储左符号的栈 void init() { while(!s.empty()) s.pop(); } void solve() { int len=strlen(str); if(len%2!=0)//如果len是奇数,证明不可能匹配成功! { cout<<"No"<<endl; return ; } for(int i=0;i<len;i++) { if(str[i]=='['||str[i]=='(') s.push(str[i]);//如果是(或者[则直接压入栈里面! else { char now=s.top(); if((now=='('&&str[i]==')')||(now=='['&&str[i]==']'))//如果遇见)或者]符号,则进行判断! { s.pop(); } else { cout<<"No"<<endl; return ; } } } cout<<"Yes"<<endl; return ; } int main() { int n; cin>>n; while(n--) { cin>>str; init(); solve(); } return 0; } </strong></span>
平衡的括号Uva-673
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。