首页 > 代码库 > POJ 1068 Parencodings

POJ 1068 Parencodings

题意:对于给出的原括号串,存在两种数字密码串:

1.p序列:当出现匹配括号对时,从该括号对的右括号开始往左数,直到最前面的左括号数,就是pi的值。

2.w序列:当出现匹配括号对时,包含在该括号对中的所有右括号数(包括该括号对,就是wi的值。

题目要求给你一个字符串的P序列,要你去求它的W序列

思路:我比较笨、菜,所以用了比较菜的方法。先用P求出字符串S,再由S求出W  ==

AC代码:

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    int i,j,num,n=0;
    cin>>n;
    while(n--)
    {
        cin>>num;
        int a,loc=0,left=0,right=0; //loc标记当前位置
        char s[40];
        int flag[40];
        memset(flag,0,sizeof(flag));    //标记匹配的括号
        for(j=0;j<num;j++)
        {
            cin>>a;
            while(left<a)
            {
                s[loc++]='(';
                left++;
            }
            flag[loc]=1;    
            s[loc++]=')';
        }
        int t;
        int cou=0;
        for(j=0;j<loc;j++)
            if(s[j]==')')
            {
                cou++;
                for(t=j-1;t>=0;t--)
                {
                    if(s[t]==')')
                    {
                        right++;
                    }
                    if(flag[t]==0)
                    {
                        if(cou==left)
                        {
                            cout<<j-t-right<<endl;
                        }
                        else
                        {
                            cout<<j-t-right<<" ";
                        }
                        flag[t]=1;
                        break;
                    }
                }
                right=0;
            }

    }
    return 0;
}