首页 > 代码库 > Poj OpenJudge 1068 Parencodings
Poj OpenJudge 1068 Parencodings
1.Link:
http://poj.org/problem?id=1068
http://bailian.openjudge.cn/practice/1068
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 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
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
Tehran 2001
3.Method:
(1)先将P-sequence转成S序列,方法为:利用vector保存,置入)前,放入当前数值减前一数值的(
(2)将S序列转为W序列,方法为:利用stack,每次遇到(则置入stack,其中-1代表“(”;遇到count = 1,直到遇到第一个(前,将stack的值累加到count,并置出
4.Code:
1 #include <iostream> 2 #include <vector> 3 #include <stack> 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<char> 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<char>::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<int> 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:
Poj OpenJudge 1068 Parencodings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。