首页 > 代码库 > [JAVA][ZOJ 1016][Parencodings]

[JAVA][ZOJ 1016][Parencodings]

Let S = s1 s2 ... s2n be a well-formed string of parentheses. S can be encoded in two different ways:

  • 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).
  • 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 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


[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. <p>  
  2. </p>import java.io.BufferedInputStream;  
  3. import java.util.Scanner;  
  4.   
  5. public class Main {  
  6.   
  7.     public static void main(String[] args) throws InterruptedException {  
  8.         Scanner sc = new Scanner(System.in);  
  9.         int n = sc.nextInt();  
  10.         for (int i = 0; i < n; i++) {  
  11.             int len = sc.nextInt();  
  12.             int P[] = new int[len];// P shows how many left parentheses have been seen since each right parentheses  
  13.             int W[] = new int[len];// W shows how many left parentheses have been seen within a pair of parentheses  
  14.             // EG:<><>,W=11  
  15.             // EG:<<>>,W=12  
  16.             // EG:<<<><>>>,W=1134  
  17.             char str[] = new char[len * 2];  
  18.             int posInP = 0;  
  19.             for (int posInStr = 0; posInStr < len; posInStr++) {  
  20.                 P[posInStr] = sc.nextInt();  
  21.   
  22.                 if (posInStr == 0) {// the first P-code  
  23.                     for (; posInP < P[posInStr]; posInP++) {  
  24.                         str[posInP] = ‘<‘;  
  25.                     }  
  26.                     str[posInP++] = ‘>‘;  
  27.                 } else {  
  28.                     if (P[posInStr] > P[posInStr - 1]) {  
  29.                         for (int k = 0; k < (P[posInStr] - P[posInStr - 1]); k++) {  
  30.                             str[posInP++] = ‘<‘;  
  31.                         }  
  32.                         str[posInP++] = ‘>‘;  
  33.                     } else {// if the next num is the same of the last  
  34.                         str[posInP++] = ‘>‘;  
  35.                     }  
  36.                 }  
  37.             }  
  38.             // check for W array  
  39.             int posInW = 0;  
  40.             for (int j = 0; j < len * 2; j++) {  
  41.                 if (str[j] == ‘<‘) {  
  42.                     continue;  
  43.                 }  
  44.                 int RightParentheses = 1;  
  45.                 for (int j2 = j - 1; j2 >= 0; j2--) {  
  46.                     if (str[j2] == ‘>‘) {  
  47.                         RightParentheses++;  
  48.                     } else {  
  49.                         RightParentheses--;  
  50.                         W[posInW]++;  
  51.                     }  
  52.                     if (RightParentheses == 0) {  
  53.                         posInW++;  
  54.                         break;  
  55.                     }  
  56.   
  57.                 }  
  58.             }  
  59.             int j;  
  60.             for (j = 0; j < len - 1; j++) {  
  61.                 System.out.print(W[j] + " ");  
  62.             }  
  63.             System.out.print(W[j]);  
  64.             System.out.println();  
  65.         }  
  66.     }  
  67. }  



PE了好多次,在Eclipse中复制2个testcase,刚复制完就出现第一个的结果,然后按回车就出现另一个结果,本来以为是这个问题,改为把所有的结果收集然后集中输出后又显示RE,最后发现居然是输出的问题,最后一个数字后面不输出空格,这细节真心不是坑爹嘛。。。。

[JAVA][ZOJ 1016][Parencodings]