嗯...

 

题目链接：https://www.luogu.org/problem/P1241

 

首先这道题是栈的入门题的加强版， 不仅要你判断这个括号序列是否合法，还要你将这个序列补充完整...

一开始是没有头绪的，看到tj之后恍然大悟...

 

思路：

我们假设所有的括号都是不合法的，即都没有匹配，然后我们从头扫一遍，对于左括号的处理比较简单：

把所有左括号的下标存入q这个手写栈，然后把所有左括号对应的右括号存入b数组中。

然后对于右括号的处理比较复杂：

如果先前的左括号都已匹配或者栈顶的左括号不与之匹配，那么将这个右括号匹配与其他匹配，即在b数组相应位置放一个左括号。如果匹配则将b数组中存的右括号清除。

输出时注意顺序...

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 char s[105], b[105]; 8 int q[105], cnt; 9 10 int main(){11     scanf("%s", s);12     int l = strlen(s);13     for(int i = 0; i < l; i++){14         if(s[i] == '(') {q[++cnt] = i; b[i] = ')'; continue;}15         if(s[i] == '[') {q[++cnt] = i; b[i] = ']'; continue;}16         if(s[i] == ')' || s[i] == ']'){17             if(!cnt || b[q[cnt]] != s[i]){18                 if(s[i] == ')') b[i] = '(';19                 else b[i] = '[';20             }21             else b[q[cnt--]] = ' ';22         }23     }24     for(int i = 0; i < l; i++){25         if(b[i] == '(' || b[i] == '[') printf("%c", b[i]);26         printf("%c", s[i]);27         if(b[i] == ')' || b[i] == ']') printf("%c", b[i]);28     }29     return 0;30 }