括号的匹配

题目 括号的匹配

image-b533275e

思路分析

思路见 括号匹配

这题多了一个优先级的问题

不过就是加了一个条件 t<0入栈时判断一下优先级 若比栈顶元素高就false

代码实现

#include<bits/stdc++.h>

using namespace std;

unordered_map<char,int> mp={

        {'{',-1},

        {'}',1},

        {'[',-2},

        {']',2},

        {'(',-3},

        {')',3},

        {'<',-4},

        {'>',4}

    };

string s;

bool check(){

    stack<int> stk;

    for(auto c:s){

        int t=mp[c];

        if(t<0){

            if(stk.size() && t>stk.top())

                return false;

            else

                stk.push(t);

        }

        else if(t>0){

            if(stk.size() && stk.top()==-t)

                stk.pop();

            else

                return false;

        }

    }

    return stk.empty();

}

int main()

{

    int n;cin>>n;

    while(n--){

        cin>>s;

        if(check())

            puts("YES");

        else

            puts("NO");

    }

    return 0;

}

同类题型

视频讲解

⬅️ 括号画家 🏠 00-刷题理模型 ➡️ 插松枝