算法题：POJ 1068 Parencodings 栈模拟

算法题：POJ 1068 Parencodings 栈模拟2014-04-12 csdn博客 accelerator_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

4 5 6 6 6 6

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

思路：模拟

代码：

#include <stdio.h>#include <string.h>int t, n, first[255], i, trans[255], ans[255], now, stack[255], num[255], top, ansn;void tra（） {int l = 0, i, j, r = 0;for （i = 1; i <= n; i ++） {for （j = 0; j < first[i] - l; j ++） {trans[now ++] = 1;}trans[now ++] = 2;r ++;l = first[i];}for （i = 0; i < l - r; i ++）trans[now ++] = 2;}void tra2（） {int i, j;for （i = 1; i < now; i ++） {if （trans[i] == 1） {stack[top ++] = trans[i];}if （trans[i] == 2） {top --;ans[ansn ++] = num[top];num[top] = 0;for （j = 0; j <= top - 1; j ++）num[j] ++;}}}int main（） {scanf（"%d", &t）;while （t --） {now = 1; top = 1; ansn = 1;memset（stack, 0, sizeof（stack））;memset（num, 0, sizeof（num））;memset（trans, 0, sizeof（trans））;memset（ans, 0, sizeof（ans））;scanf（"%d", &n）;for （i = 1; i <= n; i ++）scanf（"%d", &first[i]）;tra（）;tra2（）;for （i = 1; i < ansn - 1; i ++）printf（"%d ", ans[i] + 1）;printf（"%d
", ans[ansn - 1] + 1）;}return 0;}