EOJ Monthly 2020.7 Sponsored by TuSimple A 打字机 - 栈-括号匹配

柔光的暖阳◎ 2023-02-27 13:36 13阅读 0赞

[https://acm.ecnu.edu.cn/contest/292/problem/A/][https_acm.ecnu.edu.cn_contest_292_problem_A]

**利用栈类似括号匹配  
末尾的a一定是操作1形成的，所以可以先将串末尾的连续的a去掉  
不可能出现b开头的串  
用操作2生成的串a和b是匹配的  
可以利用栈进行匹配  
如果一个b前面有多个a 那这个时候就有两种可能 即不快乐**  
**遇到a就压栈，遇到b就弹一个出来  
最后栈里面还有a就是不快乐  
如果遇到一个b这个时候栈是空的 那就是非法的 Dead Fang**

#include <iostream>
    #include <stdio.h>
    #include <string>
    #include <string.h>
    #include <stack>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    int main()
    { 
        int T;
        cin>>T;
        for(int t=0;t<T;t++){ 
            string s;
            cin>>s;
            stack<char> st;
            if(s[0]=='b'){ 
                cout<<"Dead Fang"<<endl;
                continue;
            }
    
            int pos =s.size()-1;
            for(int i=s.size()-1;i>=0;i--){ 
                if(s[i]=='a'){ 
                    pos --;
                }else{ 
                    break;
                }
            }
    
            s = s.substr(0,pos+1);
    
            bool isS = false;
            for(int i = 0;i < s.size();i++){ 
                if(s[i]=='a'){ 
                    st.push('a');
                }else if(s[i]=='b'){ 
                    if(st.empty()){ 
                       cout<<"Dead Fang"<<endl;
                       isS = true;
                       break;
                    }
                    st.pop();
                }
            }
            if(!isS){ 
                if(!st.empty()){ 
                    cout<<"Sad Fang"<<endl;
                }else{ 
                    cout<<"Happy Fang"<<endl;
                }
            }
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

[https_acm.ecnu.edu.cn_contest_292_problem_A]: https://acm.ecnu.edu.cn/contest/292/problem/A/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20230209/77eb34070fc54fcda1153eb9b4ae064b.png