括号匹配

题目 括号匹配

image-3b23b28a

思路分析

可以用栈模拟 左括号全入栈 与右括号做比对

左括号碰到对应的右括号就出栈

但是单纯的符号不方便做比较

不妨把它们用哈希表映射成相反数

unordered_map<char,int> mp={

{'<',-1},

{'>',1},

{'(',-2},

{')',2},

{'[',-3},

{']',3},

{'{',-4},

{'}',4}

};

代码实现

#include<bits/stdc++.h>

using namespace std;

int main()

{

    unordered_map<char,int> mp={

        {'<',-1},

        {'>',1},

        {'(',-2},

        {')',2},

        {'[',-3},

        {']',3},

        {'{',-4},

        {'}',4}

    };

    string str;

    cin>>str;

    bool res=true;

    stack<int> stk;

    for(auto c:str){

        int t=mp[c];

        if(t<0)

            stk.push(t);

        else{

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

                stk.pop();

            }

            else{

                res=false;

                break;

            }

        }

    }

    if(stk.size())

        res=false;

    if(res)

        cout<<"yes"<<endl;

    else

        cout<<"no"<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 弹出序列 🏠 00-刷题理模型 ➡️ 括号画家