blablabla

样例

#include<iostream>
#include<stack>
#include<string.h>
using namespace std;


int p[128];
bool is_vaild(char* s){
    stack<char> st;
        int len=strlen(s);
        for(int i=0;i<len;i++){
            if(s[i]=='{'||s[i]=='['||s[i]=='('||s[i]=='<'){

                if(st.empty()||!st.empty()&&p[st.top()]>=p[s[i]]) st.push(s[i]);
                else return false;
            }
            else{
                //注意判空，每次使用st.pop()或者st.top() ,都要提前判断栈是否为空
                if(st.empty()) return false;  
                if(s[i]==')'&&st.top()=='('
                ||s[i]==']'&&st.top()=='['
                ||s[i]=='}'&&st.top()=='{'
                ||s[i]=='>'&&st.top()=='<') st.pop();
                else return false;
            }
        }
        if(!st.empty()) return false;
        return true;
}
int main(){
    int n;
    p['{']=4,p['[']=3,p['(']=2,p['<']=1;
    scanf("%d",&n);
    while(n--){
        char s[110];
        scanf("%s",s);
        if(is_vaild(s)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla