C/C++语言100题练习计划 78——括号序列（前缀和实现）

名人说：故立志者，为学之心也；为学者，立志之事也。—— 王阳明
进度：C/C++语言100题练习计划专栏，目前78/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description
小明有一个括号序列(一个全是左括号与右括号的序列)，我们都知道左括号和右括号作为一对括号称为一对匹配，但是右括号和左括号作为一对括号就不能称作一对匹配。比如说")(“,”(()“,”)()“等这类序列中存在不能组成的匹配的括号，称该序列为非法序列。但是如”(())“,”(()())"等这类所有括号都能找到与之匹配的序列，就称该序列为合法序列。小明想让你帮帮他看一下他现在的这个序列是否为合法序列。

2.输入输出

Input

第一行为一行长度为n的括号序列

Output

如果是合法序列输出"Yes"(不包含双引号)，如果不是合法序列输出"No"(不包含双引号)

3.测试样例

Sample Input

()())

Sample Output

No

★提示：
对于100%的数据：n<10000

二、源码实现

#include
#include
#include
using namespace std;
//借助前缀和(/差分)来实现括号匹配查找
char line[10010];//括号序列
int flag[10010];//前缀和数组

int main()
{
	//输入括号序列
	scanf("%s",line+1);
	//计算括号序列长度
	int len = strlen(line+1); 

	for(int i=1; i<=len; ++i)
	{
		if(line[i]=='(')flag[i] = 1; //出现左括号则+1，出现右括号则-1
		else flag[i] = -1;
		flag[i]+=flag[i-1];//求前缀和
	}
	
	//定义f为1，用于标记
	int f = 1;
	for(int i=1; i<=len; ++i) //判断左右括号顺序是否合法
	{
		if(flag[i]<0)
		{
			f = 0;
			break;
		}
	}
	
	//判断左右括号数是否相等
	if(flag[len])
	{
		f=0;
	}
	//如果是合法序列，输出Yes
	if(f)
		printf("Yes");
	//如果不是合法序列，输出No
	else
		printf("No");
	printf("\n");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

★关于前缀和：

1️⃣前缀和简介
前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而练习计划77中的差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以让我们在解决一些问题时变得更加得心应手。
简单来说：我们有一个数组a和它的前缀和数组s，他们满足以下公式。
s0 = a0
s1 = a0 + a1
s2 = a0 + a1 + a2
…
即 s[n]=a[1]+a[2]+…+a[n]。
例如：
a[5] = {1,2,3,4,5}
s[5] = {1,3,6,10,15}
详细运算如下：
s[1]=a[1]=1;
s[2]=a[1]+a[2]=3;
…
s[5]=a[1]+a[2]+a[3]+a[4]+a[5]=15

2️⃣求前缀和运算
//首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
const int N=1e5+10;
int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3]…a[i];
for(int i=1;i<=n;i++)
{
    sum[i]=sum[i-1]+a[i];
}

三、测试结果

()())
No

--------------------------------
Process exited after 1.663 seconds with return value 0
请按任意键继续. . .

1
2
3
4
5
6
7

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ღ( ´･ᴗ･` )比心