CodeForces 190C STL

Portal: http://codeforces.com/problemset/problem/190/C

一道卡输入输出的蛋疼题

题意：给你一个由pair和int所组成的沙茶字符串(最大含有1e5个单词)，输出合法的pair序列

这道题可以拿栈做，也就是vector或stack

呵呵 (vector==stack)=1

Examples

Input

3
pair pair int int int

Output

pair<pair<int,int>,int>

 1 #include<iostream>
 2 #include<cstring>
 3 #include<sstream>
 4 #include<vector>
 5 using namespace std;
 6 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 7 #define FORD(i,j,k) for(int i=j;i>=k;i--)
 8 #define maxn 100010
 9 #define SZ(x) int(x.size())
10 int k;
11 int a[maxn];
12 pair<int,int> res[maxn];
13 vector<int> zz;
14 string s;
15 stringstream ss,ans;
16 void cq(int l)
17 {
18     if(a[l])
19     {
20         ans<<"pair<";
21         cq(res[l].first);
22         ans<<',';
23         cq(res[l].second);
24         ans<<'>';
25     }
26     else ans<<"int";
27     return;
28 }
29 int main()
30 {
31     getline(cin,s);
32     getline(cin,s);
33     ss<<s;
34     while(!ss.eof())
35     {
36         ss>>s;
37         a[++k]=(s=="pair");
38     }
39     FORD(i,k,1)
40     {
41         if(a[i])
42         {
43             if(SZ(zz)<2)
44             {
45                 cout<<"Error occurred"<<endl;
46                 return 0;
47             }
48             res[i].first=zz.back();
49             zz.pop_back();
50             res[i].second=zz.back();
51             zz.pop_back();
52         }
53         zz.push_back(i);
54     }
55     if(SZ(zz)>1) {    
56             cout<<"Error occurred"<<endl;
57             return 0;
58             }
59     cq(1);
60     cout<<ans.str();
61     return 0;
62 }

无敌的sstream与蛋疼的getline

然后除了这个反人类的倒着处理我还写了个正着来的

 1 #include<iostream>
 2 #include<cstring>
 3 #include<sstream>
 4 using namespace std;
 5 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 6 #define FORD(i,j,k) for(int i=j;i>=k;i--)
 7 #define maxn 100010
 8 #define SZ(x) int(x.size())
 9 string s;
10 stringstream ss,ans;
11 bool cq()
12 {
13     if(ss.eof()) return false;
14     ss>>s;
15     if(s=="pair")
16     {
17         ans<<"pair<";
18         if(!cq()) return false;
19         ans<<',';
20         if(!cq()) return false;
21         ans<<'>';
22     }
23     else ans<<"int";
24     return true;
25 }
26 
27 int main()
28 {
29     getline(cin,s);
30     getline(cin,s);
31     ss<<s;
32     if(cq()&&ss.eof()) cout<<ans.str(); else cout<<"Error occurred"<<endl;
33     return 0;
34 }

爽！

总之就是各种sstream大法好啦~

#include<sstream>
stringstream ss;

ss<<s;
ss>>s;
ss.eof()