一道水题,我解决不了,求高手贴代码
题目描述
假如给你一个由’(‘和’)’组成的一个随机的括号序列,当然,这个括号序列肯定不能保证是左右括号匹配的,所以给你的任务便是去掉其中的一些括号,使得剩下的括号序列能够左右括号匹配且长度最长,即最长的合法括号序列。
输入
测试数据包括多个,每个测试数据只有一行,即一个随机的括号序列,该括号序列的长度保证不超过int表示范围。
输出
对于每个测试案例,输出一个整数,表示最后剩下的最长合法括号序列长度。
样例输入
(())()
(()
样例输出
6
2
[解决办法]
用一个栈来实现。
对于一个新的括号,做如下处理:
1. 如果是一个左括号:(,入栈。
2. 如果是一个右括号,查看栈顶的括号
2.1如果是左括号,则出栈
2.2如果是右括号,则将新括号入栈。
结束的时候,栈中剩余的括号个数既为需要去除的括号个数。
[解决办法]
用一个变量n记录左括号的个数,nSum表示总括号数
当遇到左括号时++n;
当遇到右括号时看n是否大于0,大于0则括nSum +=2 ,--n,否则不做改变
最后输出nSum即可
[解决办法]
- C/C++ code
#include <stdio.h>void main(){ char sz[100000]; while (scanf("%s",sz) != EOF) { int nLeft=0, nSum = 0; for (int i=0 ;;++i) { if (sz[i] == 0) break; if (sz[i] == '(') ++nLeft; else if ( sz[i] == ')') { if (nLeft >0) { --nLeft; nSum+=2; } } } printf("%d\n",nSum); }}