February 22, 2018

# 題目

13272 Bracket Sequence

You are given a bracket sequence B . The bracket sequence may contain 4 types of brackets:

1. Round brackets ( or )
2. Curly brackets { or }
3. Square brackets [ or ]
4. Angle brackets < or >

For each position in the bracket sequence B , you need to output the length of the longest balanced contiguous bracket sequence starting from (and including) that particular position.

Formally, a bracket sequence T is balanced if

• T is empty
• T is (P) , [P] , {P} , <P> where P is a balanced bracket sequence
• T is P Q where P and Q are balanced bracket sequences.

For example, for B = (<>)>< , the answer is ‘4 2 0 0 0 0’.

Input

First line of the input will contain a single positive integer T (T ≤ 10) denoting the number of test cases. Hence T cases follow. Each case is a single line of non-empty bracket sequence, containing only 8 types of characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’, ‘<’, ‘>’. Each of these bracket sequences will not contain more than 105 characters.

If it helps, most of the judge data is produced randomly. First a random bracket sequence (not necessarily balanced) of certain length is generated. Say it is X . Then we change X by replacing some substring of it with a random balanced bracket sequence several times.

Output

For each test case, output case number (no trailing space after ‘ Case x:’ ), followed by the answers in separate line. There is NO empty line between cases. For details, please see the sample.

Sample Input

5
()
<>
(<>)><
()()
{[[}


Sample Output

Case 1:
2
0
Case 2:
2
0
Case 3:
4
2
0
0
0
0
Case 4:
4
0
2
0
Case 5:
0
0
0
0


## Hint

• T is P Q where P and Q are balanced bracket sequences.

• T is empty

() 之類的算是 balanced ，

• T is (P) , [P] , {P} , <P> where P is a balanced bracket sequence

({}) 或是 ({}[]) 這樣遞迴(巢狀)的也算是。

# 程式碼

## C++

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>

template <typename Iterator>
void output(int nth_test_case, Iterator begin, Iterator end);
void answer(const std::string& bracket_sequence, std::vector<int>& results);

int main()
{
int test_cases;

// read num of test cases from stdin
std::cin >> test_cases;

for (int current_test_case = 1; current_test_case <= test_cases; ++current_test_case)
{
// for storing bracket_sequence
std::string bracket_sequence;

// for storing results
std::vector<int> results;

// if meet EOF or something goes wrong
if (!(std::cin >> bracket_sequence)) break;

// output the results
output(current_test_case, results.cbegin(), results.cend());
}
return 0;
}

template <typename Iterator>
void output(int nth_test_case, Iterator begin, Iterator end)
{
std::stringstream output_buf;
output_buf << "Case " << nth_test_case << ":\n";
while (begin != end) output_buf << *(begin++) << "\n";
std::cout << output_buf.str();
}

// return true if the char is a left bracket
inline bool is_left_bracket(char bracket)
{ return bracket == '(' or bracket == '{' or bracket == '[' or bracket == '<'; }

// return true if the two chars are pare of brackets else false
inline bool is_pair_of_brackets(char left, char right)
{
switch (left)
{
case '(': return right == ')';
case '{': return right == '}';
case '[': return right == ']';
case '<': return right == '>';
default: return false;
}
}

void answer(const std::string& bracket_sequence, std::vector<int>& results)
{
// get length of the sequence
auto length = bracket_sequence.length();

// use as stack
// use to store indexes of left brackets
std::deque<int> stack;

// init
results.resize(length + 1, 0);

// temporal variable
char bracket;

// for rule 1 and 2
for (int i = 0; i < length; ++i)
{
bracket = bracket_sequence[i];

// if the char is a left bracket then push the index into the stack
if (is_left_bracket(bracket)) stack.push_back(i);
// else if the current char and the last one in the stack are pair of brackets
else if (!stack.empty() and is_pair_of_brackets(bracket_sequence[stack.back()], bracket))
{
// pop last index
int position = stack.back();
stack.pop_back();

// find out the length
// +1 since the starting point is included
results[position] = i - position + 1;
}
// if it doesn't eligible to the balanced rule
else stack.clear();
}

// for rule 3
for (int i = static_cast<int>(length) - 1; i >= 0; --i)
results[i] += results[i + results[i]];