括号配对问题（栈的应用）

Description

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 s₁ and s₂ be a RBS then the strings <s₁>s₂, {s₁}s₂, [s₁]s₂,(s₁)s₂ 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 of s does not exceed 10⁶.

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.

Sample Input

Input

[<}){}

Output

Input

{()}[]

Output

Input

]]

Output

Impossible

题意：
　　　　输入一个有括号组成的字符串，只可以改变左括号，算出最少要改变多少次才能使括号配对。
方法：
　　　　先输入一个字符串s，计算字符串长度K，定义一个栈st，i从0到K，如果s[i]为右括号，判断栈是否为空，若为空输出Impossible，若st.top()为对应的左括号则删除，否则记录sum++表示要修改的次数。

  1 #include<cstdio>
  2 #include<stack>
  3 #include<string.h>
  4 using namespace std;
  5 int main()
  6 {
  7     char s[1000000+11];
  8     int k,sum;
  9     while(scanf("%s",&s)!=EOF)    
 10     {
 11     
 12         sum=0;
 13         stack<char>st;
 14         k=strlen(s);
 15         for(int i = 0; i < k ; i++)
 16         {
 17             if(s[i] == '>')
 18             {
 19                 if(st.empty())
 20                 {
 21                      printf("Impossible
");
 22                      sum=-1;
 23                      break;    
 24                 }
 25                 if(st.top() == '<')
 26                 {
 27                     st.pop();
 28                 }    
 29                 else
 30                 {
 31                     sum++;
 32                     st.pop();
 33                 }
 34             }
 35             else if(s[i] == ']')
 36             {
 37                 if(st.empty())
 38                 {
 39                      printf("Impossible
");
 40                      sum=-1;
 41                      break;        
 42                 }
 43                 if(st.top() == '[')
 44                 {
 45                     st.pop();
 46                 }
 47                 else
 48                 {
 49                     sum++;
 50                     st.pop();
 51                 }
 52             }
 53             else if(s[i] == ')')
 54             {
 55                 if(st.empty())
 56                 {
 57                      printf("Impossible
");
 58                      sum=-1;
 59                      break;        
 60                 }
 61                 if(st.top() == '(')
 62                 {
 63                     st.pop();
 64                 }
 65                 else
 66                 {
 67                     sum++;
 68                     st.pop();
 69                 }
 70             }
 71             else if(s[i] == '}')
 72             {
 73                 if(st.empty())
 74                 {
 75                      printf("Impossible
");
 76                      sum=-1;
 77                      break;        
 78                 }
 79                 if(st.top() == '{')
 80                 {
 81                     st.pop();
 82                 }
 83                 else
 84                 {
 85                     sum++;
 86                     st.pop();
 87                 }
 88             }
 89             else 
 90                 st.push(s[i]);
 91         }
 92         if(sum != -1)
 93         {
 94             if(!st.empty()) 
 95                  printf("Impossible
");
 96              else
 97                  printf("%d
",sum);
 98         }
 99     }
100     
101 }

——将来的你会感谢现在努力的自己。