时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

Given a string of balanced parentheses output all the matching pairs.

输入

A string consisting of only parentheses ‘(‘ and ‘)’. The parentheses are balanced and the length of the string is no more than 100000.

输出

For each pair of matched parentheses output their positions in the string.

样例输入

(())()()

样例输出

1 4
2 3
5 6
7 8

题意

输出可以匹配的每一对括号的位置,按照左括号位置升序输出

思路

用stack标记’(‘的位置,扫一遍,遇到’)’就匹配最近的’(‘,用vector来存数对。

代码

#include<bits/stdc++.h>
using namespace std; int main() {
stack<int> p;
char s[];
while(~scanf("%s", s)) {
vector<pair<int, int> > aa;
int len = strlen(s);
while(!p.empty()) p.pop();
for(int i = ; i < len; i++) {
if(s[i] == '(')
p.push(i + );
else if(s[i] == ')') {
int x = p.top(); p.pop();
aa.push_back(pair<int, int>(x, i + ));
}
}
sort(aa.begin(), aa.end());
for(int i = ; i < aa.size(); i++) {
printf("%d %d\n", aa[i].first, aa[i].second);
}
}
return ;
}

最新文章

  1. 我的angularjs源码学习之旅1——初识angularjs
  2. 用 正则表达式 限定XML simpleType 定义
  3. 通过servlet实现几个网站常用的功能
  4. 在win7环境下安装python2.6.6
  5. SQL Server中字符串函数LEN 和 DATALENGTH辨析
  6. nodeJS代码实现计算交社保是否合适
  7. 超实用的JavaScript技巧及最佳实践(上)
  8. NoClassDefFoundError: org/hibernate/annotations/common/reflection/ReflectionManager 解决方法
  9. MySQL出现无法删除行记录
  10. Sphnix创建文档
  11. Angular企业级开发(7)-MVC之控制器
  12. 用phpcms如何将静态页面制作成企业网站(下)
  13. SUM游戏
  14. Delphi 添加外部Form单元的方法!
  15. Zabbix WMI监控
  16. SNF软件开发机器人2018最新更新内容
  17. [福建集训2011][LOJ10111]相框
  18. phpstorm 不能自动打开上次的历史文件
  19. Nginx + Keepalived负载均衡
  20. Event IO Process

热门文章

  1. WPF 利用RichTextBox 打印出不同颜色的文本
  2. 动态规划——独立任务最优调度(Independent Task Scheduling)
  3. nginx安装http2.0协议
  4. python笔记3----第一个小爬虫
  5. 自己对WEBGL坐标系的转换过程的理解【如图】
  6. [luogu4037 JSOI2008] 魔兽地图 (树形dp)
  7. python装饰器实现登陆验证
  8. python第二周:数据类型、列表、字典
  9. Spring JDBC模板类—org.springframework.jdbc.core.JdbcTemplate(转)
  10. EF Code First:实体映射,数据迁移,重构