一般的括号匹配问题是这样的:
给出一个字符串,判断这个括号匹配是不是合法的括号匹配。
如"((" 和 "())"都不是合法的括号匹配,但是"()()()","(()())()"等就是合法的括号匹配。
这个问题解决起来非常简单,相信大家都知道怎么解决。
一般的括号匹配问题是这样的:
给出一个字符串,判断这个括号匹配是不是合法的括号匹配。
如"((" 和 "())"都不是合法的括号匹配,但是"()()()","(()())()"等就是合法的括号匹配。
这个问题解决起来非常简单,相信大家都知道怎么解决。
第一行是一个整数n,表示字符串的个数;
接下来n行是n个非空字符串,全部由'('和')'组成。
1 <= n <= 3 * 105,字符串的长度之和不超过3 * 105。
一个整数,表示满足条件的字符串对的数量。
3 () ( )
2
5 (() ))))) ()()() ((( ))
1
暴力求解,随机选择两个字符串,然后判断是否合法,只能达到部分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;
}
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"; //以上都没有问题,说明字符匹配成功 } }
费了好长时间终于搞明白了,呼哈~~~~! 献给前端的同志们。。。 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)
#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; }我本来的思路是用传统方法来判断是否为正确的表达式,就是用一个stack来判断我的第一个函数isPer函数,然后输入的时候先判断是否正确,正确就让sum++,不正确的就存入一个字符串的vector,再用一个双重循环来判断哪些符合的,但是这样只能通过百分之80,超时了,然后参考了下面的牛友的ac代码发现一个更好的思路,就是删除()然后用正负号来表示,但是中有一个坑,那就是当删除()后的字符串的第一个字符为‘(’时,是无需判断的,因为剩下的字符串只能有一种就是'('但是如果第一个字符为')'时就有可能存在'('需要判断一下,另外,我在ac代码的基础上做了一点点改变 ,我把内层循环的j的初始值设为i+1,因为不符合的和自己不可能组成符合要求的。
基本思想是参考前面几位大佬们的思想:
找出只有”()“的串 -- 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
elsebreak;
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++;elsev--;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;
}