10 solutions

  • 2
    @ 2022-1-1 21:57:08

    (看了谢队和牛肉好的代码，感觉他们的更好理解)

    我想的就是在普通的括号匹配上加点分类讨论

    #include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	while(n--){
		stack<char>S;
		string s;
		cin>>s;
		int len=s.length();
		for(int i=0;i<len;i++){
            //如果栈为空并且读到右括号，显然不合法
			if(S.empty()&&(s[i]=='>'||s[i]==')'||s[i]==']'||s[i]=='}')){
				S.push('m');//随便放个元素方便结尾的判断
				break;
			}
			else if(S.empty()) S.push(s[i]);//栈空且读到左括号则入栈
			else if(!S.empty()){//对栈非空的讨论
                //这里连着三个if来特判非法的包含关系
				if(s[i]=='('&&S.top()=='<')
					break;
				else if(s[i]=='['&&(S.top()=='('||S.top()=='<'))
					break;
				else if(s[i]=='{'&&(S.top()=='('||S.top()=='<'||S.top()=='['))
					break;
                //开始匹配
				else if(s[i]=='>'&&S.top()=='<')
					S.pop();
				else if(s[i]==')'&&S.top()=='(')
					S.pop();
				else if(s[i]==']'&&S.top()=='[')
					S.pop();
				else if(s[i]=='}'&&S.top()=='{')
					S.pop();
				else S.push(s[i]);
			}
		}
        //栈空则说明合法
		if(S.empty())cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}
  • 1
    @ 2022-4-2 14:29:29 
    #include <iostream>
#include <map>
#include <stack>
#include <cmath>
#include <string>

using namespace std;

map<char, int> m;


int main05(void) {
	m['<'] = 1;	m['>'] = -1;
	m['('] = 2;	m[')'] = -2;
	m['['] = 3;	m[']'] = -3;
	m['{'] = 4;	m['}'] = -4;

	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		stack<char> s;
		string str;
		cin >> str;
		bool flag = true;// 默认是 YES 
		for (int j = 0; j < str.size(); j++) {
			if (s.empty()) {
				s.push(str[j]);
			}
			else {
				int ch = s.top();
				if (m[ch] < m[str[j]]) {
					flag = false;
					break;
				}
				else if(m[ch] + m[str[j]] == 0) {
					s.pop();
				}
				else {
					s.push(str[j]);
				}
			}
		}
		if (flag && s.empty()) {
			cout << "YES" << endl;
		}
		else if (flag && !s.empty()) {
			cout << "NO" << endl;
		}
		else if (flag == false) {
			cout << "NO" << endl;
		}
		
	}

	return 0;
}
    • 1
      @ 2022-1-14 22:51:42 
      #include<bits/stdc++.h>
#include<string.h>
using namespace std;
int n;
char s[105];
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		stack<char> st;
		for(int j=0;j<strlen(s);j++)
		{
			if(!st.empty())//判断非法包含关系 
			{
				if(s[j]=='('&&st.top()=='<')
					break;
				else if(s[j]=='['&&(st.top()=='<'||st.top()=='('))
					break;
				else if(s[j]=='{'&&(st.top()=='['||st.top()=='('||st.top()=='<'))
					break;
			}
			
			if(s[j]=='{'||s[j]=='<'||s[j]=='('||s[j]=='['){
				st.push(s[j]);
			}
			else if(s[j]=='}'){
				if(st.empty()){
					st.push(s[j]);
					break;
				}
				else{
					if(st.top()=='{')
						st.pop();		
				}
			}
			else if(s[j]=='>'){
				if(st.empty()){
					st.push(s[j]);
					break;
				}
				else{
					char a=st.top();
					if(a=='<')
						st.pop();		
				}
			}
			else if(s[j]==']'){
				if(st.empty()){
					st.push(s[j]);
					break;
				}
				else{
					if(st.top()=='[')
						st.pop();	
				}
			}
			else if(s[j]==')'){
				if(st.empty()){
					st.push(s[j]);
					break;
				}
				else{
					if(st.top()=='(')
						st.pop();		
				}
			}
		}
		if(st.empty())
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}
      • 1
        @ 2022-1-3 13:26:41

        反面教材：

        #include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	while(n--){
		char i[260];
		scanf("%s",i);
		int k=strlen(i);
		stack<char> pp;
		if(i[0]=='>'||i[0]=='}'||i[0]==']'||i[0]==')'||i[k-1]=='<'||i[k-1]=='{'||i[k-1]=='['||i[k-1]=='('){
			cout<<"NO"<<endl;
			continue;
		}
		pp.push(i[0]);
		int l=0;
		for(int c=1;c<k-1;c++){
			if(i[c]=='<'){
				pp.push(i[c]);
			}else if(i[c]=='('){
				if(i[c-1]=='<'){
					l=1;
					break;
				}
				else pp.push(i[c]);
			}else if(i[c]=='['){
				if(i[c-1]=='('||i[c-1]=='<'){
					l=1;
					break;
				}else pp.push(i[c]);
			}else if(i[c]=='{'){
				if(i[c-1]=='<'||i[c-1]=='('||i[c-1]=='['){
					l=1;
					break;
				}else pp.push(i[c]);	
			}else if(i[c]=='>'){
				if(pp.empty()){
					l=1;
					break;
				}
				if(pp.top()=='<') pp.pop();
				else pp.push(i[c]);
			}else if(i[c]==')'){
				if(i[c+1]=='>'){
					l=1;
					break;
				}else{
					if(pp.empty()){
						l=1;
						break;
					}
					if(pp.top()=='(') pp.pop();
					else pp.push(i[c]);
				}
			}else if(i[c]==']'){
				if(i[c+1]==')'||i[c+1]=='>'){
					l=1;
					break;
				}else{
					if(pp.empty()){
						l=1;
						break;
					}
					if(pp.top()=='[') pp.pop();
					else pp.push(i[c]);
				}
			}else if(i[c]=='}'){
				if(i[c+1]==']'||i[c+1]==')'||i[c+1]=='>'){
					l=1;
					break;
				}else{
					if(pp.empty()){
						l=1;
						break;
					}
					if(pp.top()=='{') pp.pop();
					else pp.push(i[c]);
				}
			}
		}
		if(l){
			cout<<"NO"<<endl;
			continue;
		}else{
			if(pp.empty()){
				cout<<"NO"<<endl;
				continue;
			}
			else{
			if(pp.top()=='('&&i[k-1]==')'){
				pp.pop();
			}else if(pp.top()=='['&&i[k-1]==']'){
				pp.pop();
			}else if(pp.top()=='{'&&i[k-1]=='}'){
				pp.pop();
			}else if(pp.top()=='<'&&i[k-1]=='>'){
				pp.pop();
			}else{
				cout<<"NO"<<endl;
				continue;
			}
			if(pp.empty()) cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}
		}	
	}
}
        • 0
          @ 2022-1-18 11:09:50

          此题可将括号转换为数字来标记优先级，这样理解以及写代码都会方便许多

          #include<iostream>
#include<cstring>
#include<stack> 
using namespace std;
const int N=1e5+7;

char a[N];
int n,flag;

int main(){

	cin>>n;
	
	while(n--){
		
		memset(a,'/0',sizeof(a));
		flag=0;
		cin>>a;
		
		stack <int> s;
		int m=strlen(a);
		for(int i=0;i<m;i++){
			
			int k=0;
			if(a[i]=='{')k=4;
			else if(a[i]=='[')k=3;
			else if(a[i]=='(')k=2;
			else if(a[i]=='<')k=1;
			else if(a[i]=='}')k=-4;
			else if(a[i]==']')k=-3;
			else if(a[i]==')')k=-2;
			else if(a[i]=='>')k=-1;
			
			if(s.empty()){
				
				if(k>0)s.push(k);
				else {
					printf("NO\n");
					flag=1;
					break;
				}
				
			}
			else{
				if(s.top()+k==0)s.pop();
				else if(s.top()>=k)s.push(k);
				else {
					printf("NO\n");
					flag=1;
					break;
				}
			}
		}
		
		if(flag==0&&s.empty())printf("YES\n");
		else if(flag==0&&!s.empty()) printf("NO\n");
	}
	return 0;
}
          • 0
            @ 2022-1-2 21:10:04 
            #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,fg;
char a[505],s[505];
stack<char> ss;
int main()
{
	scanf("%d",&n);
    while(n--)
    {
    	fg=1;
    	scanf("%s",s);
    	for (int i=0;i<strlen(s);++i)
		{
            if (s[i]=='<')a[i]=1;if (s[i]=='>')a[i]=2;//转化为数字方便比较 
            if (s[i]=='(')a[i]=3;if (s[i]==')')a[i]=4;
            if (s[i]=='[')a[i]=5;if (s[i]==']')a[i]=6;
            if (s[i]=='{')a[i]=7;if (s[i]=='}')a[i]=8;
		}
    	for(int i=0;i<strlen(s);++i)
    	{
    		if(ss.empty()) ss.push(a[i]);
    		else
    		{
    			if(a[i]%2!=0)
    			{
    				if(ss.top()>=a[i]) ss.push(a[i]);
    				else
    				{
    					fg=0;
    					break;
					}
				}
				else
				{
					if(ss.top()!=a[i]-1)
					{
						fg=0;
						break;
					}
					else
					{
						ss.pop();
					}
				}
			}
		}
		if(fg==0||!ss.empty()) printf("NO\n");
		else printf("YES\n");
		while(!ss.empty()) ss.pop();
	}
    return 0;
}
            • 0
              @ 2022-1-2 20:19:34 
              

#include<stdio.h>
#include<stack>
#include <vector>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{  
    int n,k;
	scanf("%d",&n);
	char a = '(',b = ')',c = '{',d = '}',e = '[',f = ']',g = '<',h = '>';
	while(n -- )
	{
		k = 1;
		char arr[225];
		scanf("%s",arr);
		stack<char>str;
		for(int i = 0;i<strlen(arr);i++)
		{
			if(arr[i]==a||arr[i]==c||arr[i]==e||arr[i]==g){
				if(str.size()==0)str.push(arr[i]);
				else{
					if(arr[i]==a){
						if(str.top()!=g)str.push(arr[i]);
					}
				else if(arr[i]==g){
					str.push(arr[i]);
				}
				else if(arr[i]==e)
				{
					if(str.top()!=g&&str.top()!=a)str.push(arr[i]);
				}
				else if(arr[i]==c){
					if(str.top()==c)str.push(arr[i]);
				}
				else{
				k = 0;
				printf("NO\n");
				break;	
				}
			}
			}
			else{
				if(str.size()==0){
				k = 0;
				printf("NO\n");
				break;	
				}
	                else if(arr[i]==b){
					if(str.top()!=a){
					k = 0;
					printf("NO\n");
					break;
					}
				}
					else if(arr[i]==d){
					if(str.top()!=c){
					k = 0;
					printf("NO\n");
					break;
					}
				}
					else if(arr[i]==f){
					if(str.top()!=e){
					k = 0;
					printf("NO\n");
					break;
					}
				}
					else if(arr[i]==h){
					if(str.top()!=g){
					k = 0;
					printf("NO\n");
					break;
					}
				}
				if(k!=0){
					str.pop();
				}
			}
			
		}
		if(k==1){
		if(str.size()==0)printf("YES\n");
		else printf("NO\n");
	}
	memset(arr,0,sizeof(arr));
	}   
	return 0;
}
              • 0
                @ 2022-1-2 19:04:55

                思路：按照栈的定义一个一个进栈，<>优先级为1,()为2，[]为3,{}为4, 若(在栈顶则输入的优先级不能小于2; 蒟蒻代码如下

                #include<bits/stdc++.h>
using namespace std;//
stack <char> s;
int main(){
	int n;
	cin>>n;
	for(int j=0;j<n;j++){
		string a;
		cin>>a;
		for(int i=0;i<a.size();i++){ 
		if(!s.empty()){//栈为空就需要压入一个，不为空就进行判断
			if(s.top()=='<'){
				if(!s.empty()&&a[i]=='>'){
					s.pop();
				}
				else if(a[i]=='<'){
					s.push(a[i]);
				}
				else{
					break;
				}
			}
			else if(s.top()=='('){
				if(a[i]=='<'||a[i]=='('){
					s.push(a[i]);
				}
				else if(!s.empty()&&a[i]==')'){
					s.pop();
				}
				else{
					break;
				}
			}
			else if(s.top()=='['){
				if(a[i]=='<'||a[i]=='('||a[i]=='['){
					s.push(a[i]);
				}
				else if(!s.empty()&&a[i]==']'){
					s.pop();
				}
				else{
					break;
				}
			}
			else if(s.top()=='{'){
				if(a[i]=='<'||a[i]=='('||a[i]=='['||a[i]=='{'){
					s.push(a[i]);
				}
				else if(!s.empty()&&a[i]=='}'){
					s.pop();
				}
				else{
					break;
				}
			}
			else{
				break;
			}
		}
		else{
			s.push(a[i]);
		}
	}
		if(!s.empty()){
			cout<<"NO"<<endl;
		}
		else{
			cout<<"YES"<<endl;
		}
		while(!s.empty()){
			s.pop();
		}
	}
	return 0;
}
                • 0
                  @ 2022-1-2 16:35:59

                  眼睛疼

                  using namespace std; 
int main(){
	int n;
	char s[256];
	cin>>n;
	while(n--){
	stack<char>a;
		scanf("%s",&s);
		int k=0;
		int len=strlen(s);
		for(int i=0;i<len;i++){
			if(s[i]=='{'){
				if(a.empty()||a.top()=='{'){
				a.push(s[i]);
				}
				else{
					cout<<"NO\n";
					k=1;
					break;
				}
			}
			else if(s[i]=='['){
				if(a.empty()||a.top()=='{'||a.top()=='['){
					a.push(s[i]);
				}
				else{
					cout<<"NO\n";
					k=1;
					break;
				}
			}
			else if(s[i]=='('){
				if(a.empty()||a.top()=='{'||a.top()=='['||a.top()=='('){
					a.push(s[i]);
				}
				else{
					cout<<"NO\n";
					k=1;
					break;
				}
			}
			else if(s[i]=='<'){
				if(a.empty()||a.top()=='{'||a.top()=='['||a.top()=='('||a.top()=='<'){
					a.push(s[i]);
				}
				else{
					cout<<"NO\n";
					k=1;
					break;
				}
			}
			else if(s[i]=='>'){
				if(!a.empty()&&a.top()=='<'){
					a.pop();
				}
				else{
					cout<<"NO\n";
					k=1;
					break;
				}
			}
			else if(s[i]==')'){
				if(!a.empty()&&a.top()=='('){
					a.pop();
				}
				else{
					cout<<"NO\n";
					k=1;
					break;
				}
			}
			else if(s[i]==']'){
				if(!a.empty()&&a.top()=='['){
					a.pop();
				}
				else{
					cout<<"NO\n";
					k=1;
					break;
				}
			}
			else if(s[i]=='}'){
				if(!a.empty()&&a.top()=='{'){
					a.pop();
				}
				else{
					cout<<"NO\n";
				k=1;
				break;
				}
			}
		}
	if(a.empty()&&k==0) cout<<"YES\n";
	else if(k==0)cout<<"NO\n";
	}
    return 0;
}
                  • 0
                    @ 2022-1-2 1:22:18

                    代码长度有点夸张，但是感觉应该很好理解

                    #include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {   stack <char> s;
        string x;
        cin>>x;
        getchar();
        int ret=1,l=x.size();//用ret记录是否符合，初始值为1，只要没有改变就基本符合
        for(int i=0;i<l;i++)
        {
        	
		 if(!s.empty())
		 {	// 正常的包裹是这样的{[(<>)]} 
			if(s.top()=='['&&x[i]=='{')
			{//‘[’是在‘{’的内层的符号，所以不能让‘{’比‘[’后出现，如果后出现就不符合
        		ret=0;break;
			}
			if(s.top()=='('&&(x[i]=='['||x[i]=='{'))//同理↑↓
			{
				ret=0;break;
			} 
			if(s.top()=='<'&&(x[i]=='('||x[i]=='['||x[i]=='{'))
			{
				ret=0;break;
			}	
	     }
	    if(s.empty()&&(x[i]=='}'||x[i]=='>'||x[i]==']'||x[i]==')') )
			{
				ret=0; break;
			}//如果栈是空的，只要进入一个反括，那么这串符号就一定不符合了
			if(x[i]=='{'||x[i]=='<'||x[i]=='('||x[i]=='[')
			{
				s.push(x[i]);
			}
        
        	if(x[i]=='}'||x[i]=='>'||x[i]==']'||x[i]==')')
        	{//正常的符号匹配（写的有点赘余了，用if其实更好）
        		switch(x[i])
        		{
        			case '}':if('{'==s.top())
        					{
        						s.pop();
							}
							else ret=0;
							break;
					case ')':if('('==s.top())
        					{
        						s.pop();
							}
							else ret=0;
							break;	
				    case '>':if('<'==s.top())
        					{
        						s.pop();
							}
							else ret=0;
							break;
					case ']':if('['==s.top())
        					{
        						s.pop();
							}
							else ret=0;
							break;	
			    }
			}	
	    }
		ret==1&&s.empty()?cout<<"YES"<<endl:cout<<"NO"<<endl;
   }//注意不仅要判断ret还要判断栈是否为空
    return 0;
}
                    • 1

                    字符串匹配问题

                    Information

                    ID
                    296
                    Time
                    1000ms
                    Memory
                    128MiB
                    Difficulty
                    7
                    Tags
                    # Submissions
                    176
                    Accepted
                    36
                    Uploaded By
                    1. About
                    2. Contact Us
                    3. Privacy
                    4. Terms of Service
                    5. Copyright Complaint
                    6. Language
                    7. Legacy mode
                    8. Theme
                    2. 蜀ICP备2021003932号-1
                    3. Worker 0, 55ms
                    4. Powered by Hydro v4.18.0 Community