括号匹配 |
||
| 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，用空格隔开。每个样例之后输出一个空行 样例输入(){}[]
样例输出2 0 0 0 SourceCKBoss |
代码如下：
#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