GitBook

这里写图片描述

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

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

#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