1.Link:
2.Content:
Parencodings
Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20077 Accepted: 12122 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 1456Write 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
264 5 6 6 6 69 4 6 6 6 6 8 9 9 9Sample Output
1 1 1 4 5 61 1 2 4 5 1 1 3 9Source
3.Method:
（1）先将P-sequence转成S序列，方法为：利用vector保存，置入）前，放入当前数值减前一数值的（
（2）将S序列转为W序列，方法为：利用stack，每次遇到（则置入stack，其中-1代表“（”；遇到count = 1，直到遇到第一个（前，将stack的值累加到count，并置出
4.Code:
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int main() 8 { 9 //freopen("D://input.txt","r",stdin);10 11 int i,j;12 13 int t;14 cin >> t;15 while(t--)16 {17 int n;18 cin >> n;19 20 int *arr_p = new int[n];21 22 for(i = 0; i < n; ++i) cin >> arr_p[i];23 24 //for(i = 0; i < n; ++i) cout << arr_p[i] << endl;25 26 27 vector v_sym;28 29 int pre_p = 0;30 for(i = 0; i < n; ++i)31 {32 for(j = pre_p; j < arr_p[i]; ++j) v_sym.push_back('(');33 v_sym.push_back(')');34 pre_p = arr_p[i];35 }36 37 vector ::size_type sym_i;38 39 //for(sym_i = 0; sym_i != v_sym.size(); ++sym_i) cout << v_sym[sym_i];40 //cout << endl;41 42 stack s_sym;// -1 (, -2 )43 for(sym_i = 0; sym_i != v_sym.size(); ++sym_i)44 {45 if('(' == v_sym[sym_i]) s_sym.push(-1);46 else47 {48 int count = 1;49 while(s_sym.top() != -1)50 {51 count += s_sym.top();52 s_sym.pop();53 }54 s_sym.pop();55 cout << count << " ";56 s_sym.push(count);57 }58 }59 cout << endl;60 61 62 63 delete [] arr_p;64 65 66 }67 68 return 0;69 }
5.Reference: