[26无验证]牛牛的括号匹配-京东2018秋

1.题目描述

如果一个括号序列中的每个左括号都有一个右括号与之完成配对，这个序列就是一个合法的括号匹配序列。
例如"((())), ()()()"是合法的括号匹配序列, 而"(((()) ()((()"不是。
牛牛得到了一系列的括号序列, 牛牛要从这个序列中任意选取两个位置进行一次交换操作, 牛牛必须进行一次且仅一次操作。
牛牛想知道能否通过这次操作, 把这个序列变为合法的括号匹配序列。
例如序列 s = "())(", 对第三个位置和第四个位置进行交换变为 s = "()()", 这是一个合法的括号匹配序列。

• 输入描述:
  输入的第一行包括测试样例数 t(1 <= t <= 1000),
  接下来的 t 行, 每行一个括号序列 s(1 <= length(s) <= 100000),表示每个括号序列。
• 输出描述:
  如果可以通过一次交换变为合法的括号匹配序列,则输出"Yes",否则输出"No"
• 输入示例:

  2
  ())(
  )))(((
  

• 输出示例:

  Yes
  No
  

2.题目解析

1. 考虑简单的情况
2. 字母串长度必须是偶数。
3. (和)个数必须相同。
4. 单个()交换后不配对。
5. 逆向思维，如何判断(``)是否匹配。
6. 括号匹配，必须是(开始

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();// 括弧完全匹配，栈为空
}

括号不匹配，是括弧匹配后，交换1次，有以下几种情况。

1. 仍然是两两配对，例如：()()。
2. 产生一对不匹配的(即两个不匹配)在前)，例如：())(或者)(()。
3. 产生两对不匹配的(即两个不匹配)在前)，例如：))((。

bool match(const string& str){
  stack<char> s;
  int count = 0; // 记录不配对)个数
  for(int i=0;i!=str.size();++i){
    if('(' == str[i]) {
        s.push('(');
    } else {
        if(s.empty()) { // 记录不配对)个数
          ++count;
          if(count > 2) return false; // 多于两个
        } 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;// 记录多余[数目
    vector<char> stack;
    for(int i=0;i<s.size();++i){
        if(s[i] == '('){
            stack.push_back('(');
        }else if(s[i] == ')'){
            if(stack.empty()){// 如果前面没有做左括号，不匹配
                ++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; // 记录不配对)个数
  for(int i=0;i!=str.size();++i){
    if('(' == str[i]) {
        s.push('(');
    } else {
        if(s.empty()) { // 记录不配对)个数
          ++count;
          if(count > 2) return false; // 多于两个
        } 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;
}