首页 > 其他分享 >括号匹配

括号匹配

时间:2022-10-26 20:35:56浏览次数:77  
标签:匹配 牛牛 合法 括号 序列 Input


 

合法的括号匹配序列被定义为:
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 Input;
cin >> Input;
stack<char> s;
int Length = Input.length();
for(int i = 0;i < Length;i ++){
if(Input[i] == ']'){
if(!s.empty() && s.top() == '['){
s.pop();
}
else{
s.push(']');
}
}
else{
s.push('[');
}
}
while(!s.empty()){
if(s.top() == '['){
Input.append("]");
s.pop();
}
else{
Input.insert(0,"[");
s.pop();
}
}
cout << Input << endl;
}

 

标签:匹配,牛牛,合法,括号,序列,Input
From: https://blog.51cto.com/u_13121994/5798382

相关文章

  • 字符串--通配符*匹配
    44. WildcardMatchingHard120177FavoriteShareGivenaninputstring(​​s​​​)andapattern(​​p​​​),implementwildcardpatternmatchingwithsupportf......
  • 计算器(带括号)
    #include<iostream>//forcoutendl#include<stack>//forstack#include<string>//forstring#include<vector>//forvector#include<algorithm>//forpow()usingname......
  • 括号配对问题
    描述现在,有一行括号序列,请你检查这行括号是否配对。第一行输入一个数N(0输出每组输入数据的输出占一行,如果该字符串中所含的括号......
  • IPtables的匹配条件
    iptables的匹配条件基本匹配条件:直接能用的条件扩展匹配条件:需要调用对应的扩展模块iptables的基本匹配条件源地址目标地址网卡名称协议类型源地......
  • Scala-模式匹配
    模式匹配简介类似于java中switch当数据满足某一个分支时,执行完毕后,就直接跳出case分支类似于default语言,分支匹配其实就是顺序匹配如果数据没有匹配任何规则......
  • CSPS2019 括号树 题解
    链的部分分我们设f[i]表示以i结尾的括号序列有多少个,那么i的实际答案就是f的前缀和显然,所有左括号和不能匹配的右括号的f均为0对于每一个能匹配的右括号i,我们找到与之......
  • MySQL 索引失效-模糊查询,最左匹配原则,OR条件等。
    索引失效介绍索引失效就是我们明明在查询时的条件为索引列(包括自己新建的索引),但是索引不能起效,走的是全表扫描。explain后可查看type=ALL。这是为什么呢?首先介绍有......
  • 正则匹配
    目录正则匹配正则表达式前戏字符组特殊符号量词小练习贪婪匹配与非贪婪匹配转义符正则表达式实战建议re模块(正则模块)re模块的补充说明、网络爬虫简介正则匹配正则表达......
  • 牛客BM76(正则表达式匹配)
    BM76正则表达式匹配具体实现:1.确定dp数组以及下标的含义dp[i][j]代表s中以i结尾的子串和p中j为结尾的子串是否匹配2.状态转移(1)p[j]为普通字符:匹配的条件是前面的字符......
  • leetcode 32. 最长有效括号 js实现
    https://leetcode.cn/problems/longest-valid-parentheses/给你一个只包含'(' 和')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。示例1:输入:s="(()"输出......