1.題目描述

如果一個(gè)括號(hào)序列中的每個(gè)左括號(hào)都有一個(gè)右括號(hào)與之完成配對(duì)，這個(gè)序列就是一個(gè)合法的括號(hào)匹配序列。
例如"((())), ()()()"是合法的括號(hào)匹配序列, 而"(((()) ()((()"不是。
牛牛得到了一系列的括號(hào)序列, 牛牛要從這個(gè)序列中任意選取兩個(gè)位置進(jìn)行一次交換操作, 牛牛必須進(jìn)行一次且僅一次操作。
牛牛想知道能否通過(guò)這次操作, 把這個(gè)序列變?yōu)楹戏ǖ睦ㄌ?hào)匹配序列。
例如序列 s = "())(", 對(duì)第三個(gè)位置和第四個(gè)位置進(jìn)行交換變?yōu)?s = "()()", 這是一個(gè)合法的括號(hào)匹配序列。

• 輸入描述:
  輸入的第一行包括測(cè)試樣例數(shù) t(1 <= t <= 1000),
  接下來(lái)的 t 行, 每行一個(gè)括號(hào)序列 s(1 <= length(s) <= 100000),表示每個(gè)括號(hào)序列。
• 輸出描述:
  如果可以通過(guò)一次交換變?yōu)楹戏ǖ睦ㄌ?hào)匹配序列,則輸出"Yes",否則輸出"No"
• 輸入示例:

  2
  ())(
  )))(((
  

• 輸出示例:

  Yes
  No
  

2.題目解析

1. 考慮簡(jiǎn)單的情況
2. 字母串長(zhǎng)度必須是偶數(shù)。
3. (和)個(gè)數(shù)必須相同。
4. 單個(gè)()交換后不配對(duì)。
5. 逆向思維，如何判斷(``)是否匹配。
6. 括號(hào)匹配，必須是(開(kāi)始

bool match(const string& str){
  stack<char> s;
  for(int i=0;i!=str.size();++i){
    if('(' == str[i]) {
        s.push('(');
    } else {
        if(s.empty()) return false; // )前必須存在(
        s.pop();// 彈出匹配的(
    }
  }
  return s.empty();// 括弧完全匹配，棧為空
}

括號(hào)不匹配，是括弧匹配后，交換1次，有以下幾種情況。

1. 仍然是兩兩配對(duì)，例如：()()。
2. 產(chǎn)生一對(duì)不匹配的(即兩個(gè)不匹配)在前)，例如：())(或者)(()。
3. 產(chǎn)生兩對(duì)不匹配的(即兩個(gè)不匹配)在前)，例如：))((。

bool match(const string& str){
  stack<char> s;
  int count = 0; // 記錄不配對(duì))個(gè)數(shù)
  for(int i=0;i!=str.size();++i){
    if('(' == str[i]) {
        s.push('(');
    } else {
        if(s.empty()) { // 記錄不配對(duì))個(gè)數(shù)
          ++count;
          if(count > 2) return false; // 多于兩個(gè)
        } else {
          s.pop();// 彈出匹配的(
        }
    }
  }
  if(count == s.size()) return true;
  return false;
}

3.參考答案

#include <bits/stdc++.h>
using namespace std;
bool check(string s){
    int right = 0;// 記錄多余[數(shù)目
    vector<char> stack;
    for(int i=0;i<s.size();++i){
        if(s[i] == '('){
            stack.push_back('(');
        }else if(s[i] == ')'){
            if(stack.empty()){// 如果前面沒(méi)有做左括號(hào)，不匹配
                ++right;
            }else{
                stack.pop_back();
            }
        }
    }
    int left = stack.size();
    if(s.size() == 2 && left == 0){ // ()特殊處理
        return false;
    }
    // 判斷
    if(right != left){
        return false;
    }else{
        if(right == 1 || right == 2){
            return true;
        }else{
            return false;
        }
    }
}
int main(){
    int n = 0;
    scanf("%d",&n);
    string res[n];
    for(int i=0;i<n;++i){
        string s;
        cin >> s;
        if(check(s)){
            res[i] = "Yes";
        }else{
            res[i] = "No";
        }
    }
    for(int i=0;i<n;++i){
        cout << res[i] << "\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
bool match(const string& str){
  if (str == "()") return false;
  if (str.size() %2 != 0) return false;
  stack<char> s;
  int count = 0; // 記錄不配對(duì))個(gè)數(shù)
  for(int i=0;i!=str.size();++i){
    if('(' == str[i]) {
        s.push('(');
    } else {
        if(s.empty()) { // 記錄不配對(duì))個(gè)數(shù)
          ++count;
          if(count > 2) return false; // 多于兩個(gè)
        } else {
          s.pop();// 彈出匹配的(
        }
    }
  }
  if(count == s.size()) return true;
  return false;
}
int main() {
  int t = 0;
  scanf("%d",&t);
  while(t--) { 
      string str;
      cin >>str;
      if(match(str)){
          printf("Yes\n");
      } else {
          printf("No\n");
      }
  }
  return 0;
}