括号匹配

约定不等于承诺〃 2022-01-07 04:37 326阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td colspan="3"> <h2>括号匹配</h2> </td> 
  </tr> 
  <tr> 
   <td align="right">Accepted : 30</td> 
   <td>&nbsp;</td> 
   <td align="left">Submit : 225</td> 
  </tr> 
  <tr> 
   <td align="right">Time Limit : 10000 MS</td> 
   <td>&nbsp;</td> 
   <td align="left">Memory Limit : 65536 KB&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

http://202.197.224.59/OnlineJudge2/index.php/Contest/read\_problem/cid/38/pid/1232

#### 题目描述 ####

有一串括号(只包含"(", ")", "\[", "\]", "\{", "\}")， 保证这一括号串是匹配的， 长度小于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
    
    
    理解不了先存着
    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<math.h>
    #include<string.h>
    #include<queue>
    #include<stack>
    using namespace std;
    
    #define maxn 100005
    
    char s[maxn];
    
    struct node
    {
       
        int k, index;//小括号0，中括号1，大括号2
        int r[4], pre;
    };
    node a[maxn];
    
    int main()
    {
       
        while(scanf("%s", s+1) != EOF)
        {
       
            int i, x;
            int val[200]={0};
            node q;
            stack <node> sta;
    
            memset(a, 0, sizeof(a));
    
            val['('] = 1;val['['] = 2;val['{'] = 3;
            val[')'] = 4;val[']'] = 5;val['}'] = 6;
    
            for(i=1; s[i]; i++)
            {
       
                a[i].k = val[s[i]];
                a[i].index = i;
    
                if(a[i].k <= 3)
                    sta.push(a[i]);
                else
                {
       
                    q = sta.top();sta.pop();
                    a[i].pre = q.index;
                    q.pre = i;
    
                    if(sta.size())
                    {
       
                        node t = sta.top();sta.pop();
                        t.r[1] += q.r[1], t.r[2] += q.r[2], t.r[3] += q.r[3];
                        t.r[ q.k ] += 1;
                        sta.push(t);
                    }
    
                    a[q.index] = q;
                }
            }
    
            int N, j;
    
            scanf("%d", &N);
    
            for(i=0; i<N; i++)
            {
       
                scanf("%d", &x);
                j = min(x, a[x].pre);
                printf("%d %d %d %d\n", a[x].pre, a[j].r[1], a[j].r[2], a[j].r[3]);
            }
            printf("\n");
        }
    
        return 0;
    }
    
    
    自己一直超时代码：
    
    #include<iostream>
    #include<stdio.h>
    
    using namespace std;
    
    #define min(a, b)(a < b ? a : b)
    
    #define N 100009
    
    char str[N];
    
    struct node
    {
       
        int y, a, b, c;
    }P[N];
    
    int main()
    {
       
        int i, j, m, x, y, a, b, c, d, q, A, B, C;
    
        while(scanf("%s", str) != EOF)
        {
       
            for(j = 0; str[j]; j++)
            {
       
                d = 1;
                q = 0;
                P[j].y = P[j].a = P[j].b = P[j].c = 0;
                a = b = c = A = B = C = 0;
    
                if(str[j] == '(')
                {
       
                    for(i = j+1; str[i]; i++)
                    {
       
                        if(str[i] == '(')
                            d++;
                        else if(str[i] == ')')
                        {
       
                            q++;
                            if(q == d)
                            {
       
                                y = i;
                                break;
                            }
                        }
                    }
                }
                if(str[j] == '[')
                {
       
                    for(i = j+1; str[i]; i++)
                    {
       
                        if(str[i] == '[')
                            d++;
                        else if(str[i] == ']')
                        {
       
                            q++;
                            if(q == d)
                            {
       
                                y = i;
                                break;
                            }
                        }
                    }
                }
                if(str[j] == '{')
                {
       
                    for(i = j+1; str[i]; i++)
                    {
       
                        if(str[i] == '{')
                            d++;
                        else if(str[i] == '}')
                        {
       
                            q++;
                            if(q == d)
                            {
       
                                y = i;
                                break;
                            }
                        }
                    }
    
                }
                for(i = j; i < y; i++)
                {
       
                    if(str[i] == ')')
                        a++;
                    else if(str[i] == '(')
                        A++;
                    else if(str[i] == '{')
                        c++;
                    else if(str[i] == '}')
                        C++;
                    else if(str[i] == '[')
                        b++;
                    else if(str[i] == ']')
                        B++;
                }
               a = min(a, A);
               b = min(b, B);
               c = min(c, C);
               P[j].y = y+1, P[j].a = a, P[j].b = b, P[j].c = c;
    
            }
    
            cin >> m;
    
            while(m--)
            {
       
                cin >> x;
    
                printf("%d %d %d %d\n", P[x-1].y, P[x-1].a, P[x-1].b, P[x-1].c);
            }
    
        }
        return 0;
    }
    
    
    ideas：
    
    知道的还是太少太少，well，well，well

转载于:https://www.cnblogs.com/Tinamei/p/4459650.html