TZOJ 4621 Grammar(STL模拟)

描述

Our strings only contain letters(maybe the string contains nothing).

Now we define the production as follows:

1. (C) --> C

2. C --> C

3. (C:num)-->repeat C num times.

Illustration: (C) or C stands for a string only contains letters. (C:num) means that we should repeat string C num times (1<=num<=9).

For example: (((ab)(cd:2)):2) --> abcdcdabcdcd.

If the length of result exceed 2^20 characters print "Too Long!" in one line.

输入

There are multiple test cases. The first is a positive integer T, indicating the number of test cases.

For each test case, there is only one line contains a justifiable string.

输出

Print the result after converting. If the length of result exceed 2^20 characters print "Too Long!" in one line.

样例输入

7
(abc)
(abc:5)
((ab)(cd:2))
(((ab)(cd:2)):2)
()
(aa(bb:3)(cc:2))
(((((((((((((((((((((((uNVZgs:2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2):2)

样例输出

abc
abcabcabcabcabc
abcdcd
abcdcdabcdcd

aabbbbbbcccc
Too Long!

题意

1. (C) --> C

2. C --> C

3. (C:num)-->repeat C num times.

题解

类似于括号匹配，如果出现右括号就把中间的字符串接起来重新插入

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxlen=1048576;
 5 
 6 int main()
 7 {
 8     int T;
 9     cin>>T;
10     while(T--)
11     {
12         stack<string>st;
13         int flag=1;
14         string s1="",s;
15         cin>>s;
16         for(int i=0;i<(int)s.size();i++)
17         {
18             if(s[i]=='(')
19             {
20                 if(!s1.empty())st.push(s1);
21                 s1="(";
22                 st.push(s1);
23                 s1.clear();
24             }
25             else if(s[i]==')')
26             {
27                 string s2="";
28                 if(!s1.empty())st.push(s1);
29                 s1.clear();
30                 while(st.top()!="(")
31                 {
32                     s2.insert(0,st.top());
33                     st.pop();
34                 }
35                 st.pop();
36                 st.push(s2);
37             }
38             else if(s[i]==':')
39             {
40                 if(!s1.empty())st.push(s1);
41                 int sum=s[++i]-'0';
42                 if((int)st.top().size()*sum>maxlen)
43                 {
44                     flag=0;
45                     break;
46                 }
47                 s1=st.top();st.pop();
48                 string s3="";
49                 while(sum--)s3+=s1;
50                 st.push(s3);
51                 s1.clear();
52             }
53             else
54                 s1+=s[i];
55         }
56         if(!flag||(int)st.top().size()>maxlen)cout<<"Too Long!
";
57         else cout<<st.top()<<'
';
58     }
59     return 0;
60 }