【dfs】Sequence Decoding

题目描述

The amino acids in proteins are classified into two types of elements, hydrophobic (nonpolar) and hydrophilic (polar). Hydrophobic and hydrophilic are denoted by H and P respectively. A protein is represented by a sequence of H and P such as PPHHHPHPH. In order to reduce the representation length of a sequence, we use the notation k[S] to denote the repeated sequence of k times sequence S,where 2 ≤ k ≤ 9. A legal sequence is defined as following.
·A sequence consists of only one character ‘H’ or ‘P’ is a legal sequence.
·Let S1 and S2 be legal sequences. Then the sequence concatenated by S1 and S2 is also a legal sequence.
·Let S be a legal sequence. Then the sequence k[S] is also a legal sequence, where 2 ≤ k ≤ 9.
For example, PHPHPHPH is encoded as 4[PH]. Note that a repeated sequence may contains repeated sequences recursively such as 2[PH4[P]4[H]].
Given a nonempty encoded protein sequence S, your job is to expand S to its original sequence.
That is, you should expand 2[PH4[P]4[H]] to PHPPPPHHHHPHPPPPHHHH.

输入

The first line is an integer n indicating the number of test cases. Each of the next n lines consists of a legal sequence composed by number digits ‘2’~’9’, ‘[’, ‘]’, ‘P’ and ‘H’.

输出

For each test case, output the expanding sequence in one line.

样例输入

3
PHPHP
2[3[P]H2[P]]
HH2[P3[H]]P

样例输出

PHPHP
PPPHPPPPPHPP
HHPHHHPHHHP

提示

·1 ≤ n ≤ 10.
·All the inputs are legal.
·The length of each input sequence is less than 50.
·The length of each expanded sequence is less than 1000.

---

【题解】：

　　一开始想着怎么用栈来模拟，后来写不出来，队友提示用dfs写就好了。

　　我就用dfs写了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5+10;
 4 char s[N];
 5 int a[N],n,T;
 6 void dfs( int L , int R ){
 7     int num = 0 ;
 8     for( int i = L ; i <= R ;i ++ ){
 9         if( s[i] == 'P' || s[i] == 'H' ){
10             printf("%c",s[i] );
11         }else if( isdigit(s[i]) ){
12             int j = i ;
13             num = 0 ;
14             while( isdigit(s[j]) && j < n ){
15                 num = num * 10 + s[i] - '0' ;
16                 j ++ ;
17             }
18             i = j - 1 ;
19         }else if( s[i] == '[' ){
20             for( int j = 0 ; j < num ; j++ )
21                 dfs( i+1 , a[i] - 1 );
22             num = 1 ;
23             i = a[i] ;
24         }else if( s[i] == ']' ){
25             continue ;
26         }
27     }
28 }
29
30 int main()
31 {
32     ios_base :: sync_with_stdio(false);
33     cin.tie(NULL) , cout.tie(NULL) ;
34     cin >> T ;
35
36     while(T--){
37         cin >> s;
38         n =  strlen( s );
39         stack<int> st;
40         for( int i = 0 ; i < n ; i++ ){
41             if( s[i] == '[' ){
42                 st.push(i) ;
43             }else if( s[i] == ']' ){
44                 int cur = st.top() ;
45                 a[cur] = i ;
46                 st.pop();
47             }
48         }
49         dfs( 0 , n-1 );
50         puts("")    ;
51     }
52     return 0;
53 }

View Code