2018 百度校招笔试题 完成括号匹配

题目描述

合法的括号匹配序列被定义为: 1. 空串""是合法的括号序列 2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列 3. 如果"X"是一个合法的序列,那么"[X]"也是一个合法的括号序列 4. 每个合法的括号序列都可以由上面的规则生成 例如"", "[]", "[][][]", "[[][]]", "[[[[]]]]"都是合法的。 牛牛现在给出一个括号序列s,牛牛允许你执行的操作是:在s的开始和结尾处添加一定数量的左括号('[')或者右括号(']')使其变为一个合法的括号匹配序列。牛牛希望你能求出添加最少的括号之后的合法的括号匹配序列是什么。

输入描述:

输入包括一个字符串s,s的长度length(1 ≤ length ≤ 50),s中只包含'['和']'。

输出描述:

输出一个字符串,表示括号完全匹配的序列。

示例1

输入

][

输出

[][]

注意这道题目只能在最前面和最后面添加[]，利用括号序列的特点处理

#include <iostream> #include <string> #include <stack> using namespace std; int main() { string str; cin >> str; int count=0; string left,right; for(auto c:str){ if(c=='[') count++; else count--; if(count<0){ left+="["; count++; } } while(count>0){ right+="]"; count--; } cout<<left+str+right<<endl; }