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

 #include <iostream>

 #include <cstdio>

 #include <stdio.h>

 #include <cstdlib>

 #include <stdlib.h>

 #include <stack>

 using namespace std;

 stack<int> s;

 int main()

 {

     int i, j, n, t, sum, past, cur;

     while (scanf("%d", &t) != EOF)

     {

         while (t--)

         {

             scanf("%d", &n);

             past = cur = ;

             for (i = ; i < n; i++)

             {

                 scanf("%d", &cur);

                 for (j = ; j < cur-past; j++)

                     s.push(-);

                 if (s.top() == -)   // 找到匹配的那个括号

                 {

                     s.pop();

                     s.push();

                 }

                 else

                 {

                     sum = s.top();

                     s.pop();

                     while ()

                     {

                         if (s.top() == -)

                             break;

                         sum += s.top();

                         s.pop();

                     }

                     s.pop();    // 弹出匹配的那个括号

                     s.push(sum+);

                 }

                 if (!i)

                     cout << s.top();

                 else

                     cout << " " << s.top();

                 past = cur;

             }

             putchar('\n');

             while (!s.empty())

                 s.pop();

         }

     }

     return ;

 }

巴特西

hdu 1361.Parencodings 解题报告

最新文章

热门文章