题解 P1739 【表达式括号匹配】

maorui_cow · 2018-12-16 20:53:23 · 题解

这道题用栈即可，遇到相对括号出栈，遇到前括号入栈，具体看代码

#include<bits/stdc++.h>
using namespace std;
map<char,char>a;
stack<char>s;
int main()
{
    a['{']='}';
    a['[']=']';
    a['(']=')';//小技巧map
    string c;
    cin>>c;
    for(int i=0; i<c.size(); i++)
    {
        if(c[i]=='{'||c[i]=='['||c[i]=='(')
        {
            s.push(c[i]);//入栈
        }
        else
        {
            if(c[i]=='}'||c[i]==']'||c[i]==')')
            {
                if(s.empty())//为空则错
                {
                    cout<<"NO"<<endl;
                    return 0;
                }
                if(a[s.top()]!=c[i])//不匹配也错
                {
                    cout<<"NO"<<endl;
                    return 0;
                }
                s.pop();//匹配出栈
            }
        }
    }
    if(s.empty())//全部匹配
    {
        cout<<"YES"<<endl;
        return 0;
    }
    cout<<"NO"<<endl;
    return 0;
}