Balanced Bracket Splits

Problem Statement

Fill Missing Brackets Kindle Direct Publishing, Amazon's e-book self-publishing platform, is working on a new feature to help authors use special text characters in different ways. They have asked for your help in beta testing a new part of the feature involving round and square brackets. Given a string that consists of characters ( , ) , [ , ] and ? , determine how many ways it can be split into two non-empty substrings such that the characters in each substring can be rearranged into a balanced string. A sequence of round and square brackets can be rearranged into a balanced sequence if and only if the number of opened and closed brackets is equal for both types of brackets. The question marks can take the place of any needed character, and the substrings together must contain the entire string. Note: A substring is a contiguous group of characters in a string. Input Format The first and only line contains the string s. Constraints s contains ( , ) , [ , ] and ? only 4 ≤ length of s