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
import java.io.BufferedInputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { new Task().solve(); } } class Task { Scanner in = new Scanner(new BufferedInputStream(System.in)) ; PrintWriter out = new PrintWriter(System.out); String pand(int cnt){ String s = "" ; while(cnt-- > 0){ s += "(" ; } return s ; } void calc(String s){ List<Integer> reslut = new ArrayList<Integer>() ; int[] dp = new int[s.length()+1] ; int[] sum = new int[s.length()+1] ; Arrays.fill(dp, -1) ; Arrays.fill(sum, 0) ; Stack<Integer> stk = new Stack<Integer>() ; for(int i = 1 ; i <= s.length() ; i++){ if(s.charAt(i-1) == ')'){ dp[i] = stk.pop() ; sum[i] = sum[i-1] ; } else{ stk.push(i) ; sum[i] = sum[i-1] + 1 ; } } for(int i = 1 ; i <= s.length() ; i++){ if(dp[i] != -1){ reslut.add(sum[i] - sum[dp[i]] + 1) ; } } out.print(reslut.get(0)) ; for(int i = 1 ; i < reslut.size() ; i++){ out.print(" " + reslut.get(i)) ; } out.println() ; } void solve() { int t = in.nextInt() ; while(t-- > 0){ int n = in.nextInt() ; int fa = 0 ; String s = "" ; for(int i = 1 ; i <= n ; i++){ int v = in.nextInt() ; int cnt = v - fa ; s += pand(cnt) + ")" ; fa = v ; } calc(s) ; } out.flush(); } }
