P1241 括号序列

贪心

大致思路： 这题其实并不难，只需要从右往左遍历一遍一遍，遇到了右括号往左找左括号。我们定义一个标记数组，把可以匹配的括号标记出来；如果没有标记到的括号，我们直接输出一对，简单粗暴。

我们可以写出如下操作：

//a是标记数组
for(int i=0;i<str.size();++i)  //从右往左遍历每一个右括号（string下标是从0开始）
{
   if(str[i]==')')  //如果是右小括号
   {
       for(int j=i-1;j>=0;--j)  //往左一个一个找它的好朋友
       {
           if(str[j]=='('&&(!a[j])) //如果找到了它的好朋友
           {
               a[i] = true;
               a[j] = true; //给它们标记一下
               break;  //循环拜拜
           }
           else if(str[j]=='['&&(!a[j])) //这里有个剪枝：如果这里有一个中括号，就说明括号串起来了（例 ([)])，直接结束循环
           {
               break;
           }
       }
   }
   if(str[i]==']')  //这边也一样
   {
       for(int j=i-1;j>=0;--j)  //遍历
       {
           if(str[j]=='['&&(!a[j]))
           {
               a[i] = true;
               a[j] = true;
               break;
           }
           else if(str[j]=='('&&(!a[j]))
           {
               break;
           }
       }
   }
} 

然后我们输出一下

for(int i=0;i<str.size();++i)  //一个一个输（这里得正着）
{
    if(!a[i])  //如果他没有好朋友
    {
        //强行分配一个
        if(str[i]=='(' || str[i]==')')
        {
            cout << "()";
        }
        else 
        {
            cout << "[]";
        }
    }
    else  //有了就直接输出
    {
        cout << str[i];
    }
}

完整代码如下（为防止 Ctrl+C ，用的是图片）：

AC 记录