问题:假如给你一个由’(‘和’)’组成的一个随机的括号序列,当然,这个括号序列肯定不能保证是左右括号匹配的,所以给你的任务便是去掉其中的一些括号,使得剩下的括号序列能够左右括号匹配且长度最长,即最长的合法括号序列。
输入:测试数据包括多个,每个测试数据只有一行,即一个随机的括号序列,该括号序列的长度保证不超过10的6次方。
输出:对于每个测试案例,输出一个整数,表示最后剩下的最长合法括号序列长度。
样例输入:
(())()
(()
样例输出:
6
2
实现代码:
#include <iostream>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
int main(int argc,char **argv){
string line;
int i,cnt=0;
stack<char> s;
for(;cin>>line;){
char *cs=new char[line.size()+1];
memset(cs,0,line.size()+1);
memcpy(cs,line.c_str(),line.size());
s.push(cs[0]);
for(cnt=0,i=1;i<line.size();++i){
if(cs[i]==')'&&!s.empty()&&s.top()=='(') {
cnt+=2;
s.pop();
}else s.push(cs[i]);
}
cout<<cnt<<endl;
delete cs;
for(;!s.empty();) s.pop();
}
return 0;
}
运行结果:
- 大小: 16.6 KB
- 大小: 16.9 KB
分享到:
相关推荐
算法与数据结构实验报告
用C-free直接运行就行,内含代码和程序,试过了行。
本文实例为大家分享了python实现寻找最长回文子序列,这一类的问题可以使用动态规划的方法去做,我之前应该有几篇博文都是关于回文序列的求解的,正好有可以复用的代码就懒得再用别的方法写了,直接套用,思想还是滑...
动态规划解决最长公共子序列问题,即寻找两个序列中公共的序列中的最长的那个,结果不唯一,只能输出一个最长公共子序列,并不能生成所有的; 可视化多文档,手动输入两个子序列,显示动态规划算法的解决表格,箭头...
所有最长公共子序列(LCS)——动态规划——Java---所有!!!所有!!!所有!!!
寻找连两个序列的最长公共子序列,并且输出最长公共子序列的长度和其中某一条序列
这个问题是寻找两个(或多个)给定序列的最长子序列,这个子序列在两个序列中都以相同的相对顺序出现。子序列不必连续,但顺序必须保持一致。 例如,对于字符串 "ABCBDAB" 和 "BDCAB",其最长公共子序列是 "BCBA"。...
C语言写的查找输入的最长的单词,无论单词多长都能查找成功,最长的单词有多个也都能输出
本程序实现功能是在一串长字符串中寻找最长字符串,代码思路清晰,每行代码都有详细注解,方便读者读懂
寻找最长不重复子串 python代码
详细介绍最长递减子设有一个整数序列A1, A2, ... An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 ...
【华为OD机试真题2023JAVA】寻找符合要求的最长子串.html
寻找最长回文串_C语言实现
主要给大家介绍了如何利用C++实现最长公共子序列与最长公共子串,文章一开始就给大家简单的介绍了什么是子序列,子串应该比较好理解就不用多介绍了,人后通过算法及示例代码详细介绍了C++实现的方法,有需要的朋友们...
此代码为实现寻找一个长字符串的最大回文序列,回文指两边对称的字符串,分为字符数为奇数和偶数两种情况。
寻找最长公共子序列的C++算法,简洁、高效。输入两个长度可控的序列,输出其公共的最长子序列。
采用java语言实现了寻找最大子序列的算法, 主要用到了动态规划的思想。
找到字符串中最长的回文子串,并返回其长度
算法寻找公共子序列 基础算法题哈哈哈哈哈哈哈哈哈哈哈哈~~~~~~~~~~