POJ 1068: Parencodings

1. 题目描述

Description

Let S = s1 s2…s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2…pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2…wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).Following is an example of the above encodings:
S        (((()()())))
P-sequence      4 5 6666
W-sequence      1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

Output

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

Sample Input

2
6
4 5 6 6 6 6
9 
4 6 6 6 6 8 9 9 9

Sample Output

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

Source

2. 分析

  题目大意是,给出一个由括号“(”和“)”组成的字符串,其中的括号都可以完全匹配,不存在多余的不能匹配的括号,记做S序列,定义S序列的两种变法方式:

  • 定义P序列P=p1p2…pn,其中pi为S序列中,第i个右括号左边的左括号的个数;
  • 定义W序列W=w1w2…wn,其中wi为S序列中,从第i个右括号向左,到与之匹配的左括号之间,所包含的右括号的个数。

  测试例中给出P序列,求对应的W序列。

  题目中限制P序列的最大长度为20,因为P序列中的每一个元素对应一个“)”,则S序列中最多有20个“)”,同时最多有20个与“(”来与“(”相匹配。由此可以得知S序列的最大长度为40。

  由于S序列的最大长度只有40,存储S序列并不会消耗太大空间,从P序列译码S序列的逻辑也不复杂,解决此题的一个直接的算法就是由P序列译码得到S序列,再由S序列编码得到对应的W序列。此外,S序列可以编码为唯一的一个P序列,P序列也可以译码为唯一的一个S序列,由这种一一对应的关系,可以猜测有一种算法,能够跳过译码S序列的步骤,直接由P序列得到对应的W序列。

3. 算法设计

3.1. 算法一

  算法一的思路是从P序列译码得到S序列,在对S序列进行编码得到W序列。

  从P序列译码得到S序列的逻辑比较简单,因为pi为S序列中第i个“)”左边的“(”的个数,那么pi – pi-1就是S序列中第i-1和第i个“)”之间“(”的个数,对于每一个pi,先在S序列中填充pi – pi-1个“(”,再追加一个“)”,即可完成从P序列到S序列的译码。

  译码函数DecodePSeq() 如下所示:

void decodePSeq(int pSeq[], int pSeqLen, char decodedStr[]) {
    int pSeqIdx = 0, cnt = pSeq[0];
    char *ptrStr = decodedStr;

    ptrStr = fillChar(ptrStr, '(', cnt);
    ptrStr = fillChar(ptrStr, ')', 1);

    for(++pSeqIdx; pSeqIdx < pSeqLen; ++pSeqIdx) {
        cnt = pSeq[pSeqIdx] - pSeq[pSeqIdx - 1];
        if (cnt > 0) {
            ptrStr = fillChar(ptrStr, '(', cnt);
            ptrStr = fillChar(ptrStr, ')', 1);
        } else {
            ptrStr = fillChar(ptrStr, ')', 1);
        }
    }
    *ptrStr = '\0';
}

char* fillChar(char *str, char chr, int rep) {
    while(rep--) {
        *str++ = chr;
    }
    return str;
}

  得到S序列后,根据题目中所描述的逻辑,编码得到W序列即可。依次访问S序列中的各个元素,对于第i个元素S[i],如果S[i]为“(“,则跳过不管;如果S[i]为“)”,则从位置i开始,向前找到最近的未进行过匹配的“(”,记下其位置为j,则S序列中i与j之间“)”的个位数,即为W序列对应S[i]处“)”的值。由于W序列的编码过程涉及括号的匹配,可以使用一个数组对S序列中各个括号的匹配情况进行标记。W序列编码函数EncodeWSeq() 如下所示:

void encodeWSeq(char str[], int strLen, int wSeq[]) {
    int i = 0, j = 0, leftParPos = 0, paired[DECODED_STR_MAX_LEN] = {0}, wSeqValue = 0;
    memset(paired, 0, DECODED_STR_MAX_LEN);

    for(i = 0, j = 0; i < strLen; ++i) {
        if(str[i] == ')') {
            wSeqValue = getWSeqValue(str, i, paired);
            wSeq[j++] = wSeqValue;
        }
    }
}

int getWSeqValue(char str[], int rightParPos, int paired[]) {
    int i = rightParPos, cnt = 1;
        while(i-- >= 0) {
            if(str[i] == '(' && paired[i] == 0) {
                paired[i] = 1;
                return cnt;
            } else if(str[i] == ')') {
                ++cnt;
            }
    }
    return cnt;
}

3.2. 算法二

  算法二的思路是在不译码出S序列的情况下,由P序列直接得到W序列。

  P序列和W序列中的值都是括号的数量,从P序列得到W序列,并不需要知道每一括号的具体位置,只要关心括号的数量就行了。定义一个新数组L,其中第i个元素L[i]的值为S序列中,第i-1个“)”与第i个“)”之间,尚未进行匹配的(多余的)“(”的个数。在对S序列的第i个“)”进行匹配前,有L[i]=P[i] – P[i-1],如果L[i]>0,则表明第i-1个“)”与第i个“)”之间,有多余的“(”可供第i个“)”匹配,匹配之后,有W[i]=1,L[i]=L[i]-1;如果L[i]=0,则表明第i-1个“)”与第i个“)”之间,没有“(”可供第i个“)”匹配,则需要向第i-1个“)”之前寻找多余的“(”来进行匹配,如果仍然没有(L[i-1]=0),则向第i-2个“)”之前寻找,以此类推······直到找到L[k]>0,表明第k个“)”之前有多余的“(”可供第i个“)”匹配,有W[i]=i-k+1,L[k]=L[k]-1。由此得到W序列的各个值。由P序列直接获取W序列的函数getWSeqFromPSeq() 如下所示:

void getWSeqFromPSeq(int pSeq[], int pSeqLen, int wSeq[]) {
    int leftParNum[MAX_P_SEQ_LENGTH] = {0}, // Number of unmatched left parenthesis between index
                                            // and the last matched right parenthesis
        i = 1, matchedLeftParPos = 0;

    leftParNum[0] = pSeq[0] - 1;
    wSeq[0] = 1;
    for (i = 1; i < pSeqLen; ++i) {
        leftParNum[i] = pSeq[i] - pSeq[i-1];
        if (leftParNum[i] > 0) {
            --leftParNum[i];
            wSeq[i] = 1;
        } else {
            matchedLeftParPos = getLastNonZeroPos(leftParNum, i);
            --leftParNum[matchedLeftParPos];
            wSeq[i] = i - matchedLeftParPos + 1;
        }
    }
}

// Use stack to keep track of the nearest non-zero position in leftParNum[] instead of the searching
// algorithm below to achieve a constant running time.
// Not necessary here since the length of P sequence is very short.
int getLastNonZeroPos(int array[], int startPos) {
    while (array[--startPos] == 0)
        ;
    return startPos;
}

  上面给出的方法还有可以进一步改进。
  时间上,getLastNonZeroPos()函数使用搜索的方法,由指定位置向前搜索leftParNum[]中第一个出现的非0值,时间复杂度为O(n)。如果在计算leftParNum[]时,使用一个栈s来记录其中非0元素的位置,则getLastNonZeroPos()只需读取s的栈顶即可得到最近的非零位置i;进行括号匹配后,–leftParNum[i],如果此时leftParNum[i] == 0,则对s进行一次出栈操作。由此可以得到O(1)的时间复杂度。
  空间上,共用到了3个数组pSeq[]、wSeq[]、leftParNum[],长度均为MAX_P_SEQ_LENGTH。由于W序列是按顺序计算出来的。可以省去wSeq[],每计算得到一个值,直接进行输出。leftParNum[]中每一个元素的初始值是pSeq[]的差分,故leftParNum[]可以直接覆盖到pSeq[],从而省去leftParNum[]。

  MAX_P_SEQ_LENGTH越大,以上改进的效果越明显。由于题目限制MAX_P_SEQ_LENGTH只有20,实际提升效果并不大,方法一和方法二也没有太大的区别。