[UVa] 13272 - Bracket Sequence

題目

Link: UVa 13272 - Bracket Sequence

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.

這句話我一直認為是 ()() 要輸出 4 0 2 0
結果這句話的意思是說 ()[] 也是 4 0 2 0

這個是我自己寫的時候遇到的問題。

其他兩點規則應該沒什麼問題,

• 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;

    // find out the answers
    answer(bracket_sequence, results);

    // 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)
{
  // less I/O overhead
  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
  // add an additional element to prevent index out of range
  results.resize(length + 1, 0);

  // temporal variable
  char bracket;

  // for rule 1 and 2
  for (int i = 0; i < length; ++i)
  {
    // for being more readable code and less pointer overhead
    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]];

  // remove the additional element
  results.pop_back();
}

Show Comments