括号匹配

我会带着你远行 2022-05-18 00:55 212阅读 0赞

### [题目 括号匹配][Link 1] ###

一般的括号匹配问题是这样的：  
给出一个字符串，判断这个括号匹配是不是合法的括号匹配。如”((” 和 “())”都不是合法的括号匹配，但是”()()()”，”(()())()”等就是合法的括号匹配。这个问题解决起来非常简单，相信大家都知道怎么解决。  
现在给出一个加强版的括号匹配问题： 给出n个由括号 ‘(’ 和 ‘)’ 组成的字符串，请计算出这些字符串中有多少对字符串满足si + sj是合法的括号匹配。如果si + sj和sj + si都是合法的括号匹配(i ≠ j)，那么这两种搭配都需要计入答案；如果对于si，si + si是合法的括号匹配，那么也需要计入答案。

输入描述:  
第一行是一个整数n，表示字符串的个数；接下来n行是n个非空字符串，全部由’(‘和’)’组成。1 <= n <= 3 \* 105，字符串的长度之和不超过3 \* 105。

输出描述:  
一个整数，表示满足条件的字符串对的数量。

输入例子1:  
3  
()  
(  
)

输出例子1:  
2

输入例子2:  
5  
(()  
)))))  
()()()  
(((  
))

输出例子2:  
1

### 解析 ###

合法判断：去除字符串中形如”()”，直到不能去除为止，若字符串被清理为空，那么字符串合法，否则字符串不合法，变成以下三种：”(…(“、”)…)”、”)…)(…(“。考虑清理之后的字符串；  
n个字符串中，合法的字符串有num1个，不合法的字符串中，只有”(…(“、”)…)”能配成一组，二重循环遍历不合法字符串，配对数为num2；  
最终结果为num1\*num1+num2。

### 代码 ###

#include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    string clean(string s){
     while(s.find("()")!=-1)
         s.erase(s.find("()"), 2);
     return s;
    }
    int main(){
     ios::sync_with_stdio(false);//取消cin于stdin的同步,提升效率
     int n;
     cin >> n;
     vector<string> str(n, "");
     string temp;
     int num1=0;
     vector<int> pool;
     for(int i=0;i<n;i++){
         cin >> temp;
         str[i] = clean(temp);
         if(str[i].length()==0)
             num1++;
         else if(str[i][0]=='(')
             pool.push_back(str[i].length());
         else if(str[i][0]==')' && str[i].find('(')==-1)
             pool.push_back(-str[i].length());
     }
     int num2=0;
     for(int i=0;i<(int)pool.size();i++)
         for(int j=i;j<(int)pool.size();j++)
             if(pool[i]+pool[j]==0)
                 num2++;
     cout<<num1*num1+num2<<endl;
    }

[Link 1]: https://www.nowcoder.com/test/question/done?tid=17035212&qid=201986#summary