Brackets, Ultimate Edition
Difficulty : Medium
Community success rate: 65%
Approved by eulerscheZahl Plopx an anonymous CodinGamer
A higher resolution is required to access the IDE
- 67
Statement
Goal
You must determine the minimum number of bracket-flipping operations needed to make a given expression valid. An expression has a valid bracketing when all the parenthesesYou can flip a bracketing element in-place by replacing it with its counterpart, e.g. replace a
<{[)abc(]}> → <{[(abc)]}>
(This is an arguably harder variant of community puzzle “Brackets, Enhanced Edition”. You may want to complete that one first.)
Input
Line 1: the number N of expressions
Next N lines: an expression
Next N lines: an expression
Output
N lines: the number F of flips needed to make the expression valid. If the expression cannot be made valid, output -1 .
Constraints
N ≤ 100
expression length ≤ 10000
number of bracketing elements ≤ 25
The expression contains no whitespace.
expression length ≤ 10000
number of bracketing elements ≤ 25
The expression contains no whitespace.
Example
Input
2 <{[(abc(]}> <{[(abc>}])
Output
1 -1
A higher resolution is required to access the IDE