删括号（谨以此篇题解纪念cjy给我灵感ac）

这道题目可以说是非常恶心了，恶心在很多东西我们从题目上看不出出来。 首先，s，t两个括号序列均合法（这一点并没有显式的说出来）；其次，每次删除括号我们必须从最近的两个由内而外的删除一对或者多对。就比如说(()())这样一个序列，你不能够删除最外层的一对括号而得到()()这样子的序列，这是不合法的。好的，有了这两点，我们分析起来就得心应手了。

我看了很多题解都是dp，说实话我理解起来比较困难，而大佬cjy的双指针思想让我眼前一亮。i,j分别表示当前需要去匹配的字符串下标，初值都是0；

对于s[i]和t[j]无非四种情况，有两种是一样的，也就是可以匹配的，这时候我们两个下标都往后移动一个，即i++,j++;

而剩余两种情况则不能成功匹配：

（1）如果s[i]=='(',t[j]==')';这时候意味着s[i]不能留下，而要删就得删除至少一对。这时候我们让i往后走去匹配括号（类似于栈的原理，这个我们在下面细说），比如说当前i往后（包括i在内）的四个字符为：(()),那么这四个我们都要删掉，因为在数组中删除操作很麻烦，所以我们可以把要删除的s[i]赋值为''，当遇到''直接跳过即可；

（2）如果s[i]==')',t[j]=='('；这时候s[i]也不能留，与上面不一样的是我们需要往前找和s[i]匹配的括号，并将者之间的合法序列都删掉（还是用到栈的思想）。

栈的思想是什么呢，我们遇到'('就sta++;遇到')'就sta--；在此过程中如果sta出现了负值，就证明这过程中的序列不合法。当遍历完之后，sta不等于0，则也不合法，就是基于这样一个思想去匹配合法地括号序列。

最后值得一提的是，当我们j==len2的时候，可能i<len1，这意味着s还没遍历完，就已经能够完全匹配t序列了。不过别高兴太早，我们还需要对s剩下的序列判断是否合法，若合法才能输出possible。还是上面那个例子，

s：(()());

t:()().

以下是全部的代码。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int i,j;
    i=j=0;
    int len1=s.size();
    int len2=t.size();
    int sta;
    while(i<len1&&j<len2)
    {
        while(s[i]=='*')
            i++;
        if(i==len1)
            break;
        if(s[i]==t[j])
        {
            i++;
            j++;
        }
        else if(s[i]=='('&&t[j]==')')
        {
            sta=0;
            while(i<len1)
            {
                if(s[i]=='*')
                {
                    i++;
                    continue;
                }
                if(s[i]=='(')
                    sta++;
                else if(s[i]==')')
                    sta--;
                s[i]='*';
                i++;
                if(sta==0)
                    break;
            }
        }
        else if(s[i]==')'&&t[j]=='(')
        {
            sta=0;
            while(i>=0)
            {
                if(s[i]=='*')
                {
                    i--;
                    continue;
                }
                if(s[i]==')')
                    sta++;
                else if(s[i]=='(')
                    sta--;
                s[i]='*';
                i--;
                j--;
                if(sta==0)
                    break;
            }
            i++;
            j++;
        }
    }
    //cout<<j<<endl;
    if(j!=len2)
        cout<<"Impossible"<<endl;
    else
    {
        sta=0;
        while(i<len1)
        {
            if(s[i]=='(')
                sta++;
            else if(s[i]==')')
                sta--;
            if(sta<0)
                break;
            i++;
        }
        if(sta==0)
            cout<<"Possible"<<endl;
        else
            cout<<"Impossible"<<endl;
    }
    return 0;
}