【CodeForces】[612C]Replace To Make Regular Bracket Sequence

问题描述

问题分析

题目要求把字符串修改为符合条件的括号的次数
必须满足左(右)括号改为另一个左(右)括号
如果不能修改就输出"Impossible"

PS:
如这种{(})也是需要修改的(2次)
所以直接在遇见左括号入栈
右括号判断与栈顶是否匹配
不相同则进行修改

 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
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
char s[1000200];
bool cmp(char a,char b) {
	if((a=='['&&b==']')||(a=='('&&b==')')||(a=='{'&&b=='}')||(a=='<'&&b=='>'))
		return true;
	else
		return false;
}
int main() {
	while(scanf("%s",s)!=EOF) {
		stack<char>a;
		int l=strlen(s);
		int cnt=0;
		bool flag=true;
		for(int i=0; i<l; i++) {
			if(s[i]=='['||s[i]=='<'||s[i]=='{'||s[i]=='(')
				a.push(s[i]);
			else if(s[i]==']'||s[i]=='>'||s[i]=='}'||s[i]==')') {
				if(a.empty()) {
					flag=false;
					break;
				} else if(!cmp(a.top(),s[i])) {
					cnt++;
				}
				a.pop();
			}
		}
		if(!a.empty())
			flag=false;
		if(flag)
			printf("%d\n",cnt);
		else
			printf("Impossible\n");
	}
	return 0;
}

题目地址:【CodeForces】[612C]Replace To Make Regular Bracket Sequence