CF 612C. Replace To Make Regular Bracket Sequence【括号匹配】

【链接】：CF

【题意】：给你一个只含有括号的字符串，你可以将一种类型的左括号改成另外一种类型，右括号改成另外一种右括号

问你最少修改多少次，才能使得这个字符串匹配，输出次数

【分析】：

本题用到了栈。如果遇上左括号，就加进栈里。如果遇上右括号，就判断栈里的左括号是否和它匹配，不匹配就加一。不论匹不匹配，判断后都要让左括号出栈。

如果最后栈不为空，或者栈在循环结束前就为空，那么不论怎么改变，左右括号都不可能刚好匹配。

【代码】：

#include<cstdio>

#include<cstring>

#include<string>

#include<iostream>

#include<sstream>

#include<algorithm>

#include<utility>

#include<vector>

#include<set>

#include<map>

#include<queue>

#include<cmath>

#include<iterator>

#include<stack>

using namespace std;

typedef __int64 LL;

const int INF=1e9+7;

const double eps=1e-7;

const int maxn=1000000;

char s[maxn+10];

int n;  

bool isle(char x)

{

    return x=='('||x=='<'||x=='['||x=='{';

}  

int cal(char x,char  y)

{

    if(x=='('&&y==')')  return 0;

    if(x=='['&&y==']')  return 0;

    if(x=='{'&&y=='}')  return 0;

    if(x=='<'&&y=='>')  return 0;

        return 1;

}

int work()

{

    n=strlen(s+1);

    stack<int>st;

    int ans=0;

    for(int i=1;i<=n;i++)

    {

        char x=s[i];

        if(isle(x))  st.push(i);

        else

        {

            if(st.empty()) return -1;

            int y=st.top();

            st.pop();

            ans+=cal(s[y],s[i]);  

        }

    }  

    if(!st.empty())  return -1;  

    return ans;  

}

int main()

{

    while(~scanf("%s",s+1))

    {

        int ans=work();

        if(~ans)  printf("%d\n",ans);

        else  puts("Impossible");

    }

    return 0;

}

巴特西

CF 612C. Replace To Make Regular Bracket Sequence【括号匹配】

最新文章

热门文章