hdu 1361.Parencodings 解题报告

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1361

题目意思: 根据输入的P-sequence , 输出对应的W-sequence. P-sequence: 表示每个右括号前有多少个左括号; W-sequence: 表示每个右括号要经过多少个左括号才能找到它能够匹配的左括号.

可以通过栈来做,边输入边处理.假设左括号用-1表示, 已经匹配好的括号(即 () ) 用1表示.那么,如果是左括号的话,就把-1压进去.直到找到匹配的括号.

以样例数据: 4 6 6 6 6 8 9 9 9 为例子

它的输入是这样的: ( ( ( ( ) ( ( ) ) ) ) ( ( ) ( ) ) )

左边加粗部分表示当前这个右括号的对应左括号,右边加粗部分表示答案

(1) 4: -1 -1 -1 -1 ---> -1 -1 -1 1

(2) 6: -1 -1 -1 1 -1 -1 ---> -1 -1 -1 1 -1 1

(3) 6: -1 -1 -1 1 -1 1 　　　 ---> -1 -1 -1 1 2

(4) 6: -1 -1 -1 1 2 　　　　　 ---> -1 -1 4

(5) 6: -1 -1 4 ---> -1 5

(6) 8: -1 5 -1 -1 ---> -1 5 -1 1

(7) 9: -1 5 -1 1 -1 ---> -1 5 -1 1 1

(8) 9: -1 5 -1 1 1　　　　　　 ---> -1 5 3

(9) 9: -1 5 3 ---> 9

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <stdio.h>
 4 #include <cstdlib>
 5 #include <stdlib.h>
 6 #include <stack>
 7 using namespace std;
 8 
 9 stack<int> s;
10 
11 int main()
12 {
13     int i, j, n, t, sum, past, cur;
14     while (scanf("%d", &t) != EOF)
15     {
16         while (t--)
17         {
18             scanf("%d", &n);
19             past = cur = 0;
20             for (i = 0; i < n; i++)
21             {
22                 scanf("%d", &cur);
23                 for (j = 0; j < cur-past; j++)
24                     s.push(-1);
25                 if (s.top() == -1)   // 找到匹配的那个括号
26                 {
27                     s.pop();
28                     s.push(1);
29                 }
30                 else
31                 {
32                     sum = s.top();
33                     s.pop();
34                     while (1)
35                     {
36                         if (s.top() == -1)
37                             break;
38                         sum += s.top();
39                         s.pop();
40                     }
41                     s.pop();    // 弹出匹配的那个括号
42                     s.push(sum+1);    
43                 }
44                 if (!i)
45                     cout << s.top();
46                 else
47                     cout << " " << s.top();
48                 past = cur;
49             }
50             putchar('
');
51             while (!s.empty())
52                 s.pop();
53         }
54     }
55     return 0;
56 }