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 9Sample Output
1 1 1 4 5 6 1 1 2 4 5 1 1 3 9Source
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，实际提升效果并不大，方法一和方法二也没有太大的区别。