C. Replace To Make Regular Bracket Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given string
s consists of opening and closing brackets of four kinds
<>,
{},
[],
(). There are two types of brackets: opening and closing. You can replace any bracket by another of the same type. For example, you can replace< by the
bracket
{, but you can't replace it by
) or
>.
The following definition of a regular bracket sequence is well-known, so you can be familiar with it.
Let's define a regular bracket sequence (RBS). Empty string is RBS. Let
s1 ands2
be a RBS then the strings<s1>s2,{s1}s2,[s1]s2,(s1)s2
are also RBS.
For example the string "[[(){}]<>]" is RBS, but the strings "[)()"
and "][()()" are not.
Determine the least number of replaces to make the string
s RBS.
Input
The only line contains a non empty string
s, consisting of only opening and closing brackets of four kinds. The length ofs does not exceed106.
Output
If it's impossible to get RBS from
s print
Impossible.
Otherwise print the least number of replaces needed to get RBS from
s.
Examples
Input
[<}){}
Output
2
Input
{()}[]
Output
0
Input
]]
Output
Impossible
该题意思大概就是要形成正确的括号形式，左括号之间可以相互变换，右括号之间也可以相互变换，但左右括号之间不能相互变换。求出最小变换次数。 可以用STL中的stack解决，但没学过就用数组进行模拟压栈。
#include<stdio.h>
#include<string.h>
int main()
{
char a[1000005],b[1000000];
int n,j=0,sum=0,sum2=0;
scanf("%s",a);
n=strlen(a);
for(int i=0;i<n;i++)
{
b[j]=a[i];
if(sum2<0)
{
printf("Impossible\n");
return 0;
}
switch(a[i])//利用ASCII码进行判断，如果匹配则弹出
{
case '{':j++;sum2++;break;
case '[':j++;sum2++;break;
case '(':j++;sum2++;break;
case '<':j++;sum2++;break;
case '}':if(b[j-1]+2==a[i]){j--;}else{j--;sum++;}sum2--;break;
case ']':if(b[j-1]+2==a[i]){j--;}else{j--;sum++;}sum2--;break;
case ')':if(b[j-1]+1==a[i]){j--;}else{j--;sum++;}sum2--;break;
case '>':if(b[j-1]+2==a[i]){j--;}else{j--;sum++;}sum2--;break;
}
}
if(sum2!=0)
{
printf("Impossible\n");
return 0;
}
printf("%d\n",sum); return 0;
}
