303145: CF612C. Replace To Make Regular Bracket Sequence

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Replace To Make Regular Bracket Sequence

题意翻译

#### 题目描述: 给定一个只含 `>`,`(`,`)`,`{`,`}`,`[`,`]`的字符串。记`<`,`(`,`{`,`[`为左括号,`>`,`)`,`}`,`]`为右括号。每次可以将任意一个左括号换为任意一个不同的左括号,或将任意一个右括号换为任意一个不同的右括号,记为一次操作。求使括号序合法的最小操作次数,若无解,输出 `impossible`。 #### 输入格式: 仅有一个字符串 $s$,由字符 `>`,`(`,`)`,`{`,`}`,`[`,`]`组成 ($1 \le |s| \le 10^6$​) 。 #### 输出格式: 输出使括号序合法的最小操作次数,若无解,输出 `impossible`。

题目描述

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_{1} $ and $ s_{2} $ be a RBS then the strings < $ s_{1} $ > $ s_{2} $ , { $ s_{1} $ } $ s_{2} $ , \[ $ s_{1} $ \] $ s_{2} $ , ( $ s_{1} $ ) $ s_{2} $ 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.

输入输出格式

输入格式


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^{6} $ .

输出格式


If it's impossible to get RBS from $ s $ print Impossible. Otherwise print the least number of replaces needed to get RBS from $ s $ .

输入输出样例

输入样例 #1

[&lt;}){}

输出样例 #1

2

输入样例 #2

{()}[]

输出样例 #2

0

输入样例 #3

]]

输出样例 #3

Impossible

Input

题意翻译

#### 题目描述: 给定一个只含 `>`,`(`,`)`,`{`,`}`,`[`,`]`的字符串。记`<`,`(`,`{`,`[`为左括号,`>`,`)`,`}`,`]`为右括号。每次可以将任意一个左括号换为任意一个不同的左括号,或将任意一个右括号换为任意一个不同的右括号,记为一次操作。求使括号序合法的最小操作次数,若无解,输出 `impossible`。 #### 输入格式: 仅有一个字符串 $s$,由字符 `>`,`(`,`)`,`{`,`}`,`[`,`]`组成 ($1 \le |s| \le 10^6$​) 。 #### 输出格式: 输出使括号序合法的最小操作次数,若无解,输出 `impossible`。

加入题单

上一题 下一题 算法标签: