[25]完成括号匹配-百度2018秋

1.题目描述

合法的括号匹配序列被定义为:

1. 空串""是合法的括号序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
3. 如果"X"是一个合法的序列,那么"[X]"也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成

例如"", "[]", "[][][]", "[[][]]", "[[[[]]]]"都是合法的。
牛牛现在给出一个括号序列s,牛牛允许你执行的操作是:在s的开始和结尾处添加一定数量的左括号('[')或者右括号(']')使其变为一个合法的括号匹配序列。牛牛希望你能求出添加最少的括号之后的合法的括号匹配序列是什么。

• 输入描述:
  输入包括一个字符串s,s的长度length(1 ≤ length ≤ 50),s中只包含'['和']'。
• 输出描述:
  输出一个字符串,表示括号完全匹配的序列。
• 输入示例:

  ][
  

• 输入示例:

  [][]
  

2.题目解析

括弧匹配问题

3.参考答案

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> 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();
    string res = string(right,'[') + s + string(left,']') ;
    cout << res << "\n";
}

#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s; 
  stack<char> stack;
  int left = 0;
  int right = 0;
  for(int i = 0; i != s.size(); ++i) { 
    if(s[i] == '[') {
        stack.push('[');        
    } else {
        if(stack.empty()){
            ++left;
        } else {
            stack.pop();
        }
    }
  }
  while(!stack.empty()){
        ++right;
        stack.pop();
  }
  cout << string(left, '[') + s + string(right, ']') << endl;
  return 0;
}

使用vector代替堆栈

#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s; 
  vector<char> vec;
  int left = 0;
  for(int i = 0; i != s.size(); ++i) { 
    if(s[i] == '[') {
        vec.push_back('[');        
    } else {
        if(vec.empty()){
            ++left;
        } else {
            vec.pop_back();
        }
    }
  }
  int right = vec.size();
  cout << string(left, '[') + s + string(right, ']') << endl;
  return 0;
}

使用计数代替堆栈

#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s; 
  stack<char> stack;
  int left = 0;
  int right = 0;
  for(int i = 0; i != s.size(); ++i) { 
    if(s[i] == '[') {
        ++right;        
    } else {
        if(0 == right){
            ++left;
        } else {
            --right;
        }
    }
  }
  cout << string(left, '[') + s + string(right, ']') << endl;
  return 0;
}

牛客题目