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
思路：模拟
代码：
#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\n", ans[ansn - 1] + 1);
}
return 0;
}
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索string
， 模拟退火算法
， integer
， of
， The
right
模拟人生3 客栈、堆栈模拟慢门、两个栈模拟一个队列、栈模拟队列、模拟人生3 同福客栈，以便于您获取更多的相关知识。