【ACM】【括号匹配】

本文主要是介绍【ACM】【括号匹配】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的

输入

第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100

输出

对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行

样例输入

4
[]
([])[]
((]
([)]

样例输出

0
0
3
2

来源

《算法艺术与信息学竞赛》

尝试-： 栈

失败 ：  [[)]]

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;int Case;
char str[110];
int num[110];
void pro(int len)
{for(int i=0;i<len;i++){switch(str[i]){case '[':num[i] = 1;break;case ']':num[i] = -1;break;case '(':num[i] = 2;break;case ')':num[i] = -2;break;}}
}
int main()
{freopen("1.txt","r",stdin);scanf("%d",&Case);while(Case -- ){scanf("%s",str);pro(strlen(str));stack<int> s;while(!s.empty()){s.pop();}int ans = 0;int len = strlen(str);for(int i=0;i<len;i++){if(num[i] > 0)s.push(num[i]);else{if(s.empty()){ans ++;}else if(!s.empty()){int top = s.top();while(top + num[i] != 0){s.pop();ans ++;if(s.empty())break;top = s.top();}if(top + num[i] == 0){s.pop();}else{s.push(num[i]);}}}}ans += s.size();cout << ans << endl;}
}<span style="color:#712015;">
<span style="color:#ff6666;"></span></span>

尝试二： 我们试试dp.

1. 首先唯一确定的是最终的结果一定是([]())[]()()()()()()()()()()[][][]之类的。

所以问题可以变成求 一个给定的串，最少删几个变成制定串。 但是问题是 我们不知道结果是什么。。。所以放弃 :(

2.再尝试下

我们先对缝隙编个号从 0,1,2...len 然后嘛, 枚举最后一个括号的中间位置。

比如嘛，f(0,k) | f(k,len). 那么就是k个缝隙。

然后答案就来了那个缝隙可能是本来就有的。那么就是f(1,k) + f(k,len)

或者是没有的后来加上去的，那么可能是自己加了一个那么就是f(2,k-1) + f(k,len).

或者是后来的那个是在右边加上去的那就是f(1,k) + f(k+1,len-1)

   或者是两边都是加上去的那就是f(2,k-1)＋f(k+1,len-1)

额，感觉好像有点麻烦..

3，

额，动归方程需要再简单点。

dp[i][j] = dp[i+1][j-1]

这篇关于【ACM】【括号匹配】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---