Replace To Make Regular Bracket Sequence ( CodeForces )

用这道题来说明一下c++比g++有更深的堆栈

先来看一下提交情况，都是一份一模一样的代码（详见下文）。

GNU C++

C++

然后顺便说一下题目的思路。

定义一个栈从左到右扫面一遍仅左括号进栈，遇到右括号就与栈顶的括号对比一下，能配对就弹出这个栈顶元素。

题目：

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 and s2 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 of s does not exceed 106.

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

Input

{()}[]

Output

Input

]]

Output

Impossible

#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int MAXN = (int) 1e6+7;

char str[MAXN];
stack<char> st;
bool ispair( int i )	// 判断是否为完美配对，如果是则不需要修改
{
	if( str[i] == ')' && st.top() == '(' )
		return 1;
	if( str[i] == ']' && st.top() == '[' )
		return 1;
	if( str[i] == '}' && st.top() == '{' )
		return 1;
	if( str[i] == '>' && st.top() == '<' )
		return 1;
	return 0;
}
int main()
{
	while( ~scanf("%s", str) )
	{
		while( !st.empty() ) st.pop();
		int len = strlen(str);
		if( len == 0 )
			printf("0\n");
		else
		{
			if( str[0] == ')' || str[0] == '}' || str[0] == ']' || str[0] == '>' )
				printf("Impossible\n");
			else
			{
				int cnt = 0;	// 计数需要修改几次
				bool flag = false;		// 记录扫描的过程中是否可以直接判定
				for( int i=0; i<len; i++ )
				{
					if( str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '<' )
							st.push(str[i]);
					else if( !st.empty() && ispair(i) )
						st.pop();
					else if( !st.empty() && str[i] == ')' || str[i] == ']' || str[i] == '}' || str[i] == '>' )
					{
						cnt ++;
						st.pop();
					}
					else
					{
						flag = true;
						break;
					}
				}
				if( !flag && st.empty() )
					printf("%d\n", cnt);
				else
					printf("Impossible\n");

			}
		}
	}

	return 0;
}