2742: 【数据结构】【栈】字符串匹配问题

本文主要是介绍2742: 【数据结构】【栈】字符串匹配问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])， ([])都应该输出NO。

输入

文件的第一行为一个整数n(0<n<20)，表示以下有多少个由括号组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。

输出

在输出文件中有N行，每行都是YES或NO。

样例输入

5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]

样例输出

YES
YES
YES
YES
NO

Code:

#include<bits/stdc++.h>
using namespace std;
string a;
int my_pre(char ch){if(ch=='<'){return 1;}else if(ch=='('){return 2;}else if(ch=='['){return 3;}else if(ch=='{'){return 4;}else{return 5;}
}
bool check(string s){stack<char>a;int k;for(int i=0;i<s.size();i++){k=my_pre(s[i]);if(k<5){if(a.empty()){a.push(k);continue;}else{if(k>a.top()){return false;}else{a.push(k);continue;}}}if(k==5){if(a.empty()){return false;}if(s[i]=='>'){if(a.top()==1){a.pop();}else{return false;}}if(s[i]==')'){if(a.top()==2){a.pop();}else{return false;}}if(s[i]==']'){if(a.top()==3){a.pop();}else{return false;}}if(s[i]=='}'){if(a.top()==4){a.pop();}else{return false;}}}}if(a.empty()){return true;}else{return false;}
}
int main(){string a;int n;cin>>n;for(int i=1;i<=n;i++){cin>>a;if(check(a)){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}

这篇关于2742: 【数据结构】【栈】字符串匹配问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---