这题的话用栈来做qwq
查看原帖
这题的话用栈来做qwq
1251781
LXZ13579楼主2024/6/6 22:40

大思路:所有左括号的位置入栈, 右括号来找左括号

#include<bits/stdc++.h> 
using namespace std;
string s;
stack<int> st; 
bool vis[1002];//vis标记过的 都是配对成功的  
int main()
{
    cin>>s;
    int len=s.size();
    for(int i=0;i<len;i++){
        if(s[i]=='['||s[i]=='('){
            //左括号入栈 栈st保存所有左括号的下标 
            //因为要找右括号 左边 出现的 第一个 左括号
            //所以右括号是不入栈的 
            st.push(i); 
        }
        else{
            //右括号
            //判断栈顶(即左边出现的第一个左括号的下标)
            if(s[i]==']'){
                if(st.empty()) continue;
                int k=st.top();
                if(s[k]=='['){
                    //配对成功 
                    vis[i]=vis[k]=true;
                    st.pop(); 
                }
            } 
            if(s[i]==')'){
                if(st.empty()) continue;
                //stack在读取top或者pop之前都必须要用empty判断一次
                //否则很可能re
                int k=st.top();
                if(s[k]=='('){
                    //配对成功 
                    vis[i]=vis[k]=true;
                    st.pop(); 
                }
            } 
        }
    }
    //输出处理 
    for(int i=0;i<len;i++){
        if(vis[i]) cout<<s[i];
        else{
            if(s[i]=='('||s[i]==')') cout<<"()";
            if(s[i]==']'||s[i]=='[') cout<<"[]";
        }
    } 
    return 0;
}
2024/6/6 22:40
加载中...