首页 > 代码库 > 一道简单的数据结构题 栈的使用(括号配对)
一道简单的数据结构题 栈的使用(括号配对)
一道简单的数据结构题
发布时间: 2017年6月3日 18:46 最后更新: 2017年6月3日 18:51 时间限制: 1000ms 内存限制: 128M
如果插入“+”和“1”到一个括号序列,我们能得到一个正确的数学表达式,我们就认为这个括号序列是合法的。例如,序列"(())()", "()"和"(()(()))"是合法的,但是")(", "(()"和"(()))("是不合法的。我们这有一种仅由“(”和“)”组成的括号序列,你必须改变一些括号,从而得到一个合法的括号序列,求最少改变多少个括号。
一个只包含"("和")"的字符串,字符串的长度n小于1000000
被改变的括号个数m
复制
()))()((()
2
#include <stdio.h> #include <stack> using namespace std; int main() { stack<int> s; char c[1000000]; int num=0; scanf("%s",c); int i=0; while(c[i]!=‘\0‘){ //注意,这里的while比while((n=getchar())!=‘\n‘)及for(i=0;i<strlen(c);i++)效率要高,否则TLE if(c[i]==‘)‘){ if(s.size()) s.pop(); else{ num++; s.push(1); } } else s.push(1); i++; } num+=s.size()/2; printf("%d",num); return 0; }
一道简单的数据结构题 栈的使用(括号配对)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。