括号匹配

Accepted : 30   Submit : 234
Time Limit : 10000 MS   Memory Limit : 65536 KB

题目描述

有一串括号(只包含"(", ")", "[", "]", "{", "}"), 保证这一括号串是匹配的, 长度小于100000, 有m个询问, 每个询问为一个整数x;对于每一个询问, 要求输出一行四个整数y, a, b, c; 表示第x个括号是跟第y个配对的, x和y之间有a对小括号, b对中括号, c对大括号。

输入

约200个样例, 每个样例第一行为一个只包含括号的长度小于100000的字符串, 第二行一个小于100000的整数m, 接下来m行每行一个整数x,x不大于括号字符串的长度, x > 0;

输出

每个询问输出一行四个整数y, a, b, c,用空格隔开。每个样例之后输出一个空行

样例输入

(){}[]
3
1
3
5
[([{()[]}])][()]
5
1
2
5
13
14

样例输出

2 0 0 0
4 0 0 0
6 0 0 0 12 2 2 1
11 1 2 1
6 0 0 0
16 1 0 0
15 0 0 0

Source

CKBoss

代码如下:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
#define N 100100
using namespace std; struct node
{
int index,k,pre,r[];//k是看它是哪种括号,pre是对应的另一半下标,r[1]是小括号,其次是中括号,大括号;
}; char str[N];
node a[N]; int main()
{
node q,t;
int i,m,x,j;
int b[]={}; b['(']=;b['[']=;b['{']=;
b[')']=;b[']']=;b['}']=; while(scanf("%s",str+)!=EOF)
{
   stack<node>sta;
     memset(a,0,sizeof(a));
for(i=;str[i];i++)
{
a[i].index=i;
a[i].k=b[str[i]];
if(a[i].k<=)
{
sta.push(a[i]);
}
else
{
q=sta.top();
sta.pop();
a[i].pre=q.index;
q.pre=i;
if(sta.size())
{
t=sta.top();
sta.pop();
t.r[]+=q.r[];t.r[]+=q.r[];t.r[]+=q.r[];
t.r[q.k]+=;
sta.push(t);
}
a[q.index]=q;
}
}
scanf("%d",&m);
for(i=;i<m;i++)
{
scanf("%d",&x);
j=min(x,a[x].pre);
printf("%d %d %d %d\n",a[x].pre,a[j].r[],a[j].r[],a[j].r[]);
}
}
return ;
}

http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1232

最新文章

  1. php正则预查
  2. 51nod1069(nim博弈)
  3. mysql varchar
  4. appfabric 简单应用
  5. CSS边框阴影效果
  6. dubbo 线程池
  7. 小程序2-基本架构讲解(一)WXML 模板
  8. 绑定Oracle Database 到 ActiveReport
  9. 移动网络应用开发中,使用 HTTP 协议比起使用 socket 实现基于 TCP 的自定义协议有哪些优势?
  10. SWT中ole/activex实践--操作word的一个例子
  11. Netbeans配置Java SE嵌入式平台(树莓派)
  12. linux 检查补丁包是否安装 名称 版本 release号
  13. Visual Event :快速查看 DOM 上绑定的 JS 事件
  14. Java多线程(六) —— 线程并发库之并发容器
  15. ASP.NET MVC 编程参考
  16. mac下的安装神奇 brew --例子 安装 mysql
  17. Maven及POM文件
  18. 【bzoj3672】[Noi2014]购票 斜率优化dp+CDQ分治+树的点分治
  19. Leecode刷题之旅-C语言/python-26.移除元素
  20. 第十章 用户数据报协议和IP分片

热门文章

  1. [Command] wc
  2. 手机CPU天梯图2018年5月最新版
  3. windows下dump文件调试
  4. java基础思维导图大全
  5. 【转】Reason: The specified virtual disk needs repair.
  6. php获取ios或android通过文件头(header)传过来的坐标,通过百度接口获取具体城市和地址,并存入到session中。
  7. 【Spring Boot&amp;&amp;Spring Cloud系列】提高数据库访问性能
  8. Excel中用countif和countifs统计符合条件的个数 good
  9. JavaScript怎样学
  10. SOA面向服务的架构