首页 > 试题广场 >

括号匹配

[编程题]括号匹配
  • 热度指数:2026 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

一般的括号匹配问题是这样的:

给出一个字符串,判断这个括号匹配是不是合法的括号匹配。

如"((" 和 "())"都不是合法的括号匹配,但是"()()()","(()())()"等就是合法的括号匹配。

这个问题解决起来非常简单,相信大家都知道怎么解决。

现在给出一个加强版的括号匹配问题: 给出n个由括号 '(' 和 ‘)’ 组成的字符串,请计算出这些字符串中有多少对字符串满足si + sj是合法的括号匹配。如果si + sj和s+ si都是合法的括号匹配(i ≠ j),那么这两种搭配都需要计入答案;如果对于sisi + si是合法的括号匹配,那么也需要计入答案。



输入描述:

第一行是一个整数n,表示字符串的个数;

接下来n行是n个非空字符串,全部由'('和')'组成。

1 <= n <= 3 * 105,字符串的长度之和不超过3 * 105



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

输入

3
()
(
)

输出

2
示例2

输入

5
(()
)))))
()()()
(((
))

输出

1
WAK头像 WAK

暴力求解,随机选择两个字符串,然后判断是否合法,只能达到部分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;

}

发表于 2018-07-20 19:58:36 回复(1)
java版本带注释,思路看wwwwQQQq得来的。假如不够细分的话只能通过80%,需要把匹配过的字符串进行处理和细分成四类。一种为空,一种全部都是(,一种全部都是),一种是有)(,最后一种情况不能成功匹配,第二种和第三种能够成功匹配,第一种自身就可以成功匹配。
import java.util.*;

public class Main{
    public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();

		List<String> leftlist = new ArrayList<>();    //接收“(”字符串
		List<String> rightlist = new ArrayList<>();    //接收")"字符串
		int count = 0;    //记录自身就能完成匹配的字符串个数
		int sum = 0;        //记录其它情况完成匹配的字符串个数
		scanner.nextLine();
		for (int i = 0; i < n; i++) {        //循环接受输入
			String s = scanner.nextLine();
			String aString = pairString(s);    //进行判断
			switch (aString) {
			case "success":    //自身满足匹配
				count++;
				break;
			case "fail":        //不可能满足匹配
				break;
			default:            //全部都是"("或")"
				if (aString.contains("(")) {
					leftlist.add(aString);
				}
				else {
					rightlist.add(aString);
				}
				break;
			}
		}

		for(String s1:leftlist) {
			for(String s2:rightlist) {        //将两种情况的字符串一一匹配
				int num1 = s1.toCharArray().length; //算出字符串长度
				int num2 = s2.toCharArray().length;
				if (num1==num2) {            //两边字符串长度相等,说明能够匹配
					sum++;
                }    
			}
		}
		
		System.out.printf("%d\n",count*count+sum);
	}

	public static String pairString(String string) {
		char[] chars = string.toCharArray();		//接受字符串进行分割

		Stack<String> stack = new Stack<>();
		for(int i = 0; i<chars.length;i++) {		//进行逐字符判断
			String s = String.valueOf(chars[i]);
            if (stack.isEmpty()){                   //栈空,直接入栈
                stack.push(s);
                continue;
            }
			if (s.equals("(")) {					//匹配到左半括号,进栈
				stack.push(s);
			}
			if (s.equals(")")) {					//匹配到右半括号
				if(!stack.isEmpty()) {
					String sl = stack.pop();							
					if(sl.equals("(")&&s.equals(")")){  //括号匹配成功,抵消
                        
                    }
					else {                        //不成功,都是")",再重新入栈
						stack.push(sl);
						stack.push(s);
					}
				}
			}
				
		}
		if (!stack.isEmpty()) {					//循环完所有字符,假如栈非空,说明有括号未进行匹配
			String s1 = stack.pop();    //取栈顶
			String ss = s1;
			while (!stack.isEmpty()) {    //将栈里元素全部取出
				String s2 = stack.pop();
				ss = ss+s2;            //拼出括号匹配剩下的字符串
				if (!s1.equals(s2)) {    //假如不是全部相同,只可能是")(",这样的字符串不能满足括号匹配
					return "fail";
				}
			}
			return ss;            //返回剩余的括号,由于都是一样的字符,所以不需要倒过来
		}
		return "success";		//以上都没有问题,说明字符匹配成功
	}
    
}


发表于 2020-07-20 17:43:13 回复(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);
}

发表于 2018-09-14 01:20:47 回复(0)
思路参考WAK的:Python解法,算法复杂度过大,AC了90%
暴力求解,随机选择两个字符串,然后判断是否合法,只能达到部分ac,对于有些例子,时间复杂度太高。后面考虑先对字符串进行一遍是否合法的判断,将本身合法的取出,个数记为num1,将本身不合法的存入vector,进行暴力求解,个数记为num2,总个数为num1num1+num2,但还是时间复杂度太高。最后考虑,先对字符串进行一遍是否合法的判断,将本身合法的取出,个数记为num1,将本身不合法的字符串中间已匹配的括号去掉,只保留不匹配的部分,不匹配的部分只有这几种情况:全是左括号;全是右括号;先是部分右括号,然后左括号。这三种里面只有前两种在个数相同时,组合起来可以合法。所以将第一种情况的字符串长度存入vecl中,将第二种情况的字符串长度存入vecr中,两层for循环,找vecl中和vecr中相同的个数,记为num2,总数为num1num1+num2。全部ac。
# 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)
编辑于 2018-08-12 13:05:09 回复(0)
  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;
    }
    
发表于 2018-07-22 01:14:53 回复(5)
#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;
}
我本来的思路是用传统方法来判断是否为正确的表达式,就是用一个stack来判断我的第一个函数isPer函数,然后输入的时候先判断是否正确,正确就让sum++,不正确的就存入一个字符串的vector,再用一个双重循环来判断哪些符合的,但是这样只能通过百分之80,超时了,然后参考了下面的牛友的ac代码发现一个更好的思路,就是删除()然后用正负号来表示,但是中有一个坑,那就是当删除()后的字符串的第一个字符为‘(’时,是无需判断的,因为剩下的字符串只能有一种就是'('但是如果第一个字符为')'时就有可能存在'('需要判断一下,另外,我在ac代码的基础上做了一点点改变 ,我把内层循环的j的初始值设为i+1,因为不符合的和自己不可能组成符合要求的。
发表于 2019-02-14 12:00:24 回复(0)

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

后来发现是通过使用list的count方法通过了所有的case (使用单层循环)。


#!/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()
		

编辑于 2018-10-19 22:28:36 回复(0)
基本上暴力解法只能过80%,所以需要优化。
判断字符串匹配思想:给一个整数c=0,遍历字符串s,碰到左括号+1,碰到有括号-1,如果遍历过程中c不出现小于0的情况且最终c=0,那么字符串s中的括号就是匹配的。
1.输入时检查每个字符串,可以分成2种:自身匹配①,自身不匹配。其中自身不匹配有三种情况:全向右开(内部可能穿插着一些自身闭合的子串 如:'(()('这种)②,全向左开③,两面开④。
2.①只能和①匹配,所以可以单独用m记录①的个数,则组合匹配的个数是m*m.
3.④跟谁都不匹配, 所以忽略。
4.②和③,哈希表positive记录②中向右开的括号的个数为key的字符串个数有多少个,哈希表negtive记录③中向左开的括号的个数为key的字符串个数有多少个。如若判断当前s为情况②,则找③中绝对值相等的字符串的个数,累加即可。
5.把2和4中的值相加,就是最终的总个数。
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String[] strs=new String[n];
        //int[] cs=new int[n];
        HashMap<Integer,Integer> positive=new HashMap<>();
        HashMap<Integer,Integer> negtive=new HashMap<>();
        int m=0,count=0;
        for(int i=0;i<n;i++)
        {
            String s=sc.next();
            int c=0,min=Integer.MAX_VALUE;
            boolean flag=false;
            for(int j=0;j<s.length();j++)
            {
                if(s.charAt(j)=='(')
                    c++;
                else if(s.charAt(j)==')')
                    c--;
                else;
                if(c<0)
                {
                    flag=true;
                    if(c<min)
                        min=c;
                }
            }
            if(!flag && c==0)
                m++;
            if(!flag && c>0)
            {
                if(positive.get(c)!=null)
                    positive.put(c, positive.get(c)+1);
                else
                    positive.put(c,1);
                if(negtive.get(-c)!=null)
                    count+=negtive.get(-c);
            }
            if(c<0 && c==min)
            {
                if(negtive.get(c)!=null)
                    negtive.put(c, negtive.get(c)+1);
                else
                    negtive.put(c,1);
                if(positive.get(-c)!=null)
                    count+=positive.get(-c);
            }
        }
        count+=m*m;
        /*for(Integer key:positive.keySet())
        {
            if(negtive.get(-key)!=null)
                count+=positive.get(key)*negtive.get(-key);    
        }*/
        System.out.println(count);
    }
}
发表于 2018-08-13 14:23:15 回复(0)

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;
}
发表于 2018-08-09 22:27:08 回复(0)
超过规定时间,总是在80%case的时候卡住。对方法尝试过各种优化方法,目前无解。
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

发表于 2018-08-08 16:31:22 回复(0)
#include<iostream>
#include<string>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int length;
    cin >> length;
    int result1 = 0;
    int result2 = 0;
    vector<stack> input;
    //读取输入字符串
    for(int i = 0;i < length;++i)
    {
        string tmp;
        cin >> tmp;
        //检验字符串是否需要存入vector里面
        stack<char> cl1;
        for(size_t idx = 0;idx < tmp.size();idx++)
        {
            if(tmp[idx] == '(')
            {
                cl1.push(tmp[idx]);
            }
            else if((!cl1.empty())&&(cl1.top() == '('))
            {
                cl1.pop();
            }
            else
            {
                cl1.push(tmp[idx]);
            }
        }
        if(cl1.empty())
        {
            result1++;
        }
        else
        {
            input.push_back(cl1);
            while(!cl1.empty())
            {
                cl1.pop();
            }
        }
    }
    stack<char> cl2;
    //对vector里面的任意两个string判断是否能够拼成合法字符串
    for(size_t i = 0;i < input.size();i++)
    {
        for(size_t j = 0;j < input.size();j++)
        {
            stack<char> stk1 = input[i];
            stack<char> stk2 = input[j];
            for(size_t idx1 = 0;idx1 < stk1.size();idx1++)
            {
                if()
            }
            if(cl2.empty())
            {
                result2++;
            }
            else
            {
                while(!cl2.empty())
                {
                    cl2.pop();
                }
            }
        }
    }
    //输出结果
    cout << (result1*result1 + result2) << endl;
    return 0;
}

发表于 2018-08-04 16:00:33 回复(0)
对每个字符串分四种情况,向右开口,向左开口,不开口,左右都开口;其中左右都开口没法和任何匹配,向右开口个数记为+数,向左开口记为-数,不开口记为0
排序后,两头向中间扫描一遍即可判断成功配对数量。
时间复杂度,O(n)+O(nlogn)+O(n)
int main()
{
    int n,i,j,count,count2,len,jieguo;
    cin>>n;
    vector<int> fix(n,0);
    for(i=0;i<n;++i){
        string str1;
        cin>>str1;
        len=str1.length();
        count=count2=0;
        for(j=0;j<len;++j){
            //括号左右开口的时候不符合规则,此时count2>0&&count>0
            if(str1[j]=='(')
                ++count;
            else{
                if(count>0)
                    --count;
                else
                    ++count2;
            }
        }
        if (count2 > 0 && count > 0)//去掉不合法的串
            fix[i]=100000;
        else
            fix[i]=count>count2?count:(-1*count2);
    }
    sort(fix.begin(), fix.end());
    j=n;
    jieguo=0;
    for(i=0;i<n;){ //i从左到右扫描,j从右到左边扫描,配对.初始i指向前元素,j指向尾元素后一位
        int temp=fix[i];
        if(temp<0){
           count=1;
           while(fix[++i]==temp && i<n)//找到count个值为temp的元素
               ++count;
           while( (fix[--j]+temp)>0 ){}//将j移动到<= (-temp) 坐标
           if( (fix[j]+temp)==0 ){ //配对
               count2=1;
               while( (fix[--j]+temp)==0 )
                   ++count2;
               jieguo=jieguo+count*count2;  
           }
           ++j;//回归初始状态    
        }
        else if(temp==0){  //配对
            count=1;
            while(fix[++i]==temp && i<n)
                ++count;           
            jieguo+=(count*count);
        }
        else
            break; 
    }
    cout<<jieguo;  
    return 0;
}

发表于 2018-07-27 10:47:25 回复(0)
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);
             
        }
    }
}

发表于 2018-07-25 21:15:06 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String ns = input.nextLine();
        int n = Integer.parseInt(ns);
        String[] strs = new String[n];
        int[][] flag = new int[n][2];
        int k = 0;
        for (int i = 0; i < n; i++) {
            strs[i] = input.nextLine();
            flag[i] = isEqual2(strs[i]);
        }
        for (int i = 0; i < n; i++) {
            if (flag[i][0] == 3) {
                for (int j = 0; j < n; j++) {
                    if (flag[j][0] == 3)
                        k++;
                }
            } else {
                if (flag[i][0] == 0) {
                    for (int h = 0; h < n; h++) {
                        if (flag[h][0] == 1 && flag[h][1] == flag[i][1])
                            k++;
                    }
                }
            }
        }
        System.out.println(k);
    }

    public static int[] isEqual2(String s) {
        int n = s.length();
        char[] ch1 = new char[n];
        int[] flag = new int[2];
        ch1 = s.toCharArray();
        Stack<Character> sc = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (ch1[i] == '(') {
                sc.push(ch1[i]);
            } else {
                if ((sc.size() > 0) && (sc.peek() == '(')) {
                    sc.pop();
                } else {
                    sc.push(ch1[i]);
                }
            }
        }
        if (sc.size() == 0) {
            flag[0] = 3;
            flag[1] = 0;
            return flag;
        } else {
            int slen = sc.size();
            char[] ch2 = new char[sc.size()];
            for (int i = sc.size() - 1; i > -1; i--) {
                ch2[i] = sc.pop();
            }
            if (ch2[0] == ch2[slen - 1]) {
                if (ch2[0] == '(') {
                    flag[0] = 0;
                    flag[1] = slen + 1;
                    return flag;
                } else {
                    flag[0] = 1;
                    flag[1] = slen + 1;
                    return flag;
                }
            } else {
                flag[0] = 2;
                flag[1] = 0;
                return flag;
            }
        }

    }
}
发表于 2018-07-21 17:19:46 回复(0)
#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;
}
编辑于 2018-07-21 11:24:00 回复(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;
}
发表于 2018-07-21 10:21:05 回复(0)