括号匹配

暴力求解，随机选择两个字符串，然后判断是否合法，只能达到部分ac，对于有些例子，时间复杂度太高。后面考虑先对字符串进行一遍是否合法的判断，将本身合法的取出，个数记为num1，将本身不合法的存入vector，进行暴力求解，个数记为num2，总个数为num1*num1+num2，但还是时间复杂度太高。最后考虑，先对字符串进行一遍是否合法的判断，将本身合法的取出，个数记为num1，将本身不合法的字符串中间已匹配的括号去掉，只保留不匹配的部分，不匹配的部分只有这几种情况：全是左括号；全是右括号；先是部分右括号，然后左括号。这三种里面只有前两种在个数相同时，组合起来可以合法。所以将第一种情况的字符串长度存入vecl中，将第二种情况的字符串长度存入vecr中，两层for循环，找vecl中和vecr中相同的个数，记为num2，总数为num1*num1+num2。全部ac。

答案：

#include<iostream>

#include<vector>

#include<stack>

#include<string>

using namespace std;

int main(){

    int n;

    while(cin>>n){

        vector<string> vec;

        vector<int> vecl;

        vector<int> vecr;

        int num1 = 0;

        for(int i = 0;i<n;i++){

            string a;

            cin>>a;

            stack<char> sta;

            for(int x = 0;x<a.size();x++){  //压栈，并去掉合法部分

                if(a[x]=='(')

                    sta.push(a[x]);

                else if(!sta.empty()&&sta.top()=='(')

                    sta.pop();

                else

                    sta.push(a[x]);

            }

            string u =  "";

            if(sta.empty())  //栈空，说明本身合法，计数加1

                num1++;

            else{           //栈不空，按左右括号，分别将个数存入vecl和vecr

                stack<char> st;

                while(!sta.empty()){

                    char s = sta.top();

                    st.push(s);

                    sta.pop();

                }

                while(!st.empty()){

                    char s = st.top();

                    st.pop();

                    u+=s;

                }

                if(u[0]=='('&&u[u.size()-1]=='(')

                    vecl.push_back(u.size());

                if(u[0]==')'&&u[u.size()-1]==')')

                    vecr.push_back(u.size());

            }

        }

        int num2 = 0;

        for(int i = 0;i<vecl.size();i++){

            for(int j = 0;j<vecr.size();j++){

                if(vecl[i]==vecr[j])

                    num2++;

            }

        }

        cout<<num2+num1*num1<<endl;

    }

    system("pause");

    return 0;

}

费了好长时间终于搞明白了，呼哈~~~~！
献给前端的同志们。。。
while(n = readline()){
    var arr = [];
    for(var i=0;i<n;i++){
        arr[i] = readline().split('');
    };
    var count = 0;
    var ln=[],rn=[];
    for(var i=0;i<n;i++){
       var j=0;
        while(j<arr[i].length-1){
            if(arr[i][j] == '(' && arr[i][j+1]==')'){
                arr[i].splice(j,2);
                
                j=0;   
            }else
                j++;
        }      
    };
    for(var i=0;i<n;i++){
         if(arr[i][0] == '(' ){
                ln.push(arr[i]);
            }else if(arr[i][0] == ')' && arr[i].indexOf('(')==-1){
                rn.push(arr[i]);
            }else if(arr[i].length == 0){
                count++;
            }
    };
var num1 = 0;
for(var i=0;i<ln.length;i++){
    for(var j=0;j<rn.length;j++){
        if(ln[i].length == rn[j].length){
            num1++;
        }
    }
}
            
    var num = count*count +num1;
    print(num);
}

# coding=utf-8
import sys
import math
num = int(sys.stdin.readline().strip())
string_list = []
for i in range(num):
    string = sys.stdin.readline().strip()
    string_list.append(string)
count = 0
def check(string):
    flag = True
    left, right = 0, 0
    for i in string:
        if i == '(':
            left += 1
        if i == ')':
            if left >0:
                left -= 1
            else:
                right += 1
        if left < right:              #出现右括号数量大于左括号数量，退出循环
            flag = False
            # return flag, left, right
    if left!= right:
        flag = False
    return flag,left,right
num1 = 0
num2 = 0
save_left =[]
save_right =[]
for string in string_list:
    flag,left,right = check(string)
    if flag :
        num1 += 1
        # print('s')
    else:
        if left == 0 and right != 0:
            save_right.append(right)
        elif left != 0 and right == 0:
            save_left.append(left)
# print(save_right,save_left)
for i in save_left :
    for j in save_right:
        if i == j:
            num2 += 1
print(num1*num1 + num2)

1. 合法判断：去除字符串中形如"()"，直到不能去除为止，若字符串被清理为空，那么字符串合法，否则字符串不合法，变成以下三种："(...("、")...)"、")...)(...("。考虑清理之后的字符串；
2. n个字符串中，合法的字符串有num1个，不合法的字符串中，只有"(...("、")...)"能配成一组，二重循环遍历不合法字符串，配对数为num2；
3. 最终结果为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);
    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;
   }
   

#include<bits/stdc++.h>
using namespace std;
int n;
bool isPer(string str){
    stack<char> val;
    int len=str.length();
    for(int i=0;i<len;i++){
        if(str[i]=='(')
            val.push('(');
        if(str[i]==')'){
            if(val.empty())
                return false;
            else
                val.pop();
        }
    }
    return val.empty();
}
string cleann(string str){
    while(str.find("()")!=-1){
        str.erase(str.find("()"),2);
    }
    return str;
}
int main(){
    cin>>n;
    vector<string> val;
    vector<int> value;
    int sum=0;
    for(int i=0;i<n;i++){
        string temp;
        cin>>temp;
        //val.push_back(temp);
        temp=cleann(temp);
        if(temp=="")
            sum++;
        else if(temp[0]=='(')
            value.push_back(temp.length());
        else if(temp[0]==')'&&temp.find('(')==-1)
            value.push_back(-temp.length());
    }
    sum*=sum;
    //long long suu=sum*sum;
    for(int i=0;i<value.size()-1;i++){
        for(int j=i+1;j<value.size();j++){
            if(value[i]+value[j]==0)
                sum++;
        }
    }
    cout<<sum<<endl;
    return 0;
}

基本思想是参考前面几位大佬们的思想：
找出只有”（）“的串 -- num1
再找分别有”（“ 和”）"
最后通过二次循环遍历比较计算出第二种情况的-- "(...(" ")...)" 组合数量num2
最后得到 num1*num1 + num2
不过我这里先用正则表达式的sub 先将所有的"()"括号对都去掉了，最后只留下具有
"(" 和 ")" 进行对比。
不过最后二次遍历时，case通过率只有60%

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


import re


def handle(brack):

    while re.findall(r"[\(][\)]", brack) != []:
        brack = re.sub(r"[\(][\)]", "", brack)
    return brack


def main():
    num = int(input().strip())
    brackets_list = []
    brackets_list2 = []
    brackets_list3 = []
    num1 = 0
    num2 = 0
    for i in range(num):
        brackets_list.append(input().strip())

    for i in range(num):
        temp = handle(brackets_list[i])
        if temp == "":
            num1 += 1
        else:
            if list(temp)[0] == ")":
                brackets_list2.append(temp)
            elif list(temp)[0] == "(":
                brackets_list3.append(temp)
    for i in brackets_list3:
        num2 += brackets_list2.count(")"*len(i))
    result = num1*num1 + num2
    print(result)


if __name__ == '__main__':
    main()
		

			
		

41ms

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#include<unordered_map>
using namespace std;
int getBackets(string s){
    int ps = 0;
    int ng = 0;
    for(int i=0;i<(int)s.length();i++){
        if(s[i] == '(') ps++;
        else{
            if(ps > 0) ps--;
            else ng++;
        }
    }
    // 既有不合法的负括号，最后正的还多余的话，这种字符串肯定是无论怎么组合都无法组成合法的
    if(ng > 0 && ps > 0) return -0x3f3f3f3f;
    //返回多余的正括号数或者负括号数
    return -1*ng+ps;
}
int main(){
//  freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    vector<int> v;
    string s;
    unordered_map<int,int> mp;
    for(int i=0;i<n;i++){
        cin>>s;
        int tmp = getBackets(s);
        if(mp.find(tmp) == mp.end()) mp[tmp] = 0;
        mp[tmp]++;
        v.push_back(tmp);
    }
    int ans = 0;
    for(int i=0;i<n;i++){
//      printf("%d ",v[i]);
        if(v[i] < 0) continue;
        else if(v[i] == 0) ans += mp[0];
        else ans += mp[-1*v[i]];
    }
    printf("%d\n", ans);
    return 0;
}

def simplify(s):
    l = [0]
    num = 0
    for c in s:
        if c == '(':
            num += 1
            l.append('(')
        elif l[-1] == '(':
            num -= 1
            l.pop()
        else:
            num -= 1
            l.append(')')
    return l[1:], num
n = input()
ss = [''] * n
for i in range(n):
    ss[i] = simplify(raw_input())
l1 = len(ss)
ss = [s for s in ss if s[0]] # exclude [] which means the string is legal
r = (len(ss) - l1) ** 2
ss = [s for s in ss if s[0][0] != ')' or s[0][-1] != '('] # exclude those won't match any string
for i in range(len(ss)):
    for j in range(i, len(ss)):
        s = ss[i][0] + ss[j][0]
        if len(s) % 2 != 0 or ss[i][1] + ss[j][1] != 0:
            continue
        if not simplify(s)[0] or not simplify(ss[j][0] + ss[i][0])[0]:
            r += 1
print r

	

        else

	importjava.util.*;



	publicclassMain{



	    publicstaticvoidmain(String[] args){



	        Scanner scanner = newScanner(System.in);



	        while(scanner.hasNextInt()){



	            intn=scanner.nextInt();



	            scanner.nextLine();



	            int[] pos=new int[400000];



	            int[] neg=new int[400000];



	            for(inti=0;i<n;i++){



	                String s=scanner.nextLine();



	                intminV=0;



	                intv=0;



	                for(intj=0;j<s.length();j++){



	                    if(s.charAt(j)=='(')



	                        v++;



	                    else



	                        v--;



	                    if(v<minV)



	                        minV=v;



	                }



	                if(v>=0&& minV>=0)



	                    pos[v]++;



	                elseif(v<0&& minV==v)



	                    neg[-v]++;



	            }



	            intresult=pos[0]*pos[0];



	            for(intj=1;j<400000;j++)



	                result+=pos[j]*neg[j];



	 



	            System.out.printf("%d\n",result);



	             



	        }



	    }



	}

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int Sum(string str,int& l){
    int len = str.size();
    //if(len<1) return 0;
    int left=0,right=0;
    for(int i=0;i<len;i++){
        if(str[i] == '(') ++left;
        else {
            ++right;
            if(right>left) {++l;
            right = left = 0;}
        }
    }
    return left-right;
    //为正，缺右括号
}
int main(){
    int n;
    while(cin>>n){
        vector<int> left;//缺左括号的次数
        vector<int> right;//缺右括号的次数
        int cnt = 0;
        int len = n;
        while(len--){
            string tem;
            cin>>tem;
            int l=0;
            right.push_back(Sum(tem,l));
            left.push_back(l);

        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(left[i]==0 && right[j]==0 && right[i]==left[j]) cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

	

#include <bitset>
#include <unordered_set>
#include <map>
#include <queue>
#include <ctime>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <string>
#include <iomanip>
#include <set>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <climits>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
auto __x = []() {cin.sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); return 0; }();
typedef long long ll;

int main()
{
    int n; cin >> n;
    map<int, int> cnt;
    for (int ni = 0; ni < n; ++ni)
    {
        string s; cin >> s;
        int c = 0;
        for (char e : s) if (e == '(') c++; else c--;
        bool valid = true;
        if (c >= 0)
        {
            int cnt = c;
            for (int i = s.size() - 1; i >= 0; --i)
            {
                if (s[i] == ')') cnt++;
                else cnt--;
                if (cnt < 0)
                {
                    valid = false;
                    break;
                }
            }
        }
        else {
            int cnt = -c;
            for (int i = 0; i < s.size(); ++i)
            {
                if (s[i] == '(')
                    cnt++;
                else cnt--;
                if (cnt < 0) {
                    valid = false;
                    break;
                }
            }
        }
        if (valid)
            cnt[c]++;
    }
    ll ans = 0;
    for (auto p : cnt)
    {
        if (p.first >= 0)
        {
            if (cnt.count(-p.first))
                ans += p.second * cnt[-p.first];
        }
    }
    cout << ans << endl;
    return 0;
}