STL-A-堆栈问题

最新推荐文章于 2024-06-13 20:18:40 发布

___TPH

最新推荐文章于 2024-06-13 20:18:40 发布

阅读量227

点赞数

本文链接：https://blog.csdn.net/TPH530539250/article/details/79133721

版权

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.

Example

Input

[<}){}

Output

Input

{()}[]

Output

Input

]]

Output

Impossible

由题意可知道一个简单的堆栈问题：

思路：

第一个括号判断为右则直接输出impossible结束，否则每次遇到新来的右半边括号就和栈顶比较，能改变或不经改变配套则消去，左括号则入栈，最后判断栈中是否有有剩余，有剩余说明无法完成。

#include<iostream>
#include<cstdio>
#include<stack>
#include<string>
using namespace std;
int main(void)
{
    stack<char>s;
    char ch;
    long int n=0;
    scanf("%c",&ch);
    if(ch!='\n'&&(ch==')'||ch=='>'||ch==']'||ch=='}')) //第一个来的就是右括号，无法被匹配，直接出I输mpossible并结束

    {
        printf("Impossible");
        return 0;
    }
    else s.push(ch); //压栈左括号
    while(scanf("%c",&ch)&&ch!='\n')
    {
        if(ch=='{'||ch=='<'||ch=='['||ch=='(')
            s.push(ch); //左括号入栈
        else if(ch==')'){ if(s.empty()) {printf("Impossible");return 0;} //右括号进行比较
            if(s.top()=='(') s.pop(); //判断非空其实可以和第一个判断合并
            else {n++;s.pop();}
        }
        else if(ch=='}'){ if(s.empty()) {printf("Impossible");return 0;}
            if(s.top()=='{') s.pop();
            else {n++;s.pop();}
        }
        else if(ch==']'){ if(s.empty()) {printf("Impossible");return 0;}
            if(s.top()=='[') s.pop();
            else {n++;s.pop();}
        }
        else if(ch=='>'){ if(s.empty()) {printf("Impossible");return 0;}
            if(s.top()=='<') s.pop();
            else {n++;s.pop();}
        }

    }
    if(!s.empty()) printf("Impossible"); //最后判断是否右剩余为被消去的
    else
    printf("%ld",n);
    return 0;
}