题解
这题用 S T L STL STL容器解比较好
方法一 s t r i n g string string
s
t
r
i
n
g
string
string每次在字符串中间插入时，时间复杂度
O
(
n
)
O(n)
O(n)
输出
O
(
n
)
O(n)
O(n)
总时间复杂度
O
(
n
)
～
O
(
n
2
)
O(n)～O(n^2)
O(n)～O(n2)
方法二 l i s t list list
l
i
s
t
list
list每次插入时间复杂度约为
O
(
1
)
O(1)
O(1)，输出
O
(
n
)
O(n)
O(n)
总时间复杂度
O
(
n
)
O(n)
O(n)
代码
#include <bits/stdc++.h>
using namespace std;
list<char> l;
int main()
{
char c;
int op = 1;
string s;
cin >> s;
list<char>::iterator it = l.begin();
for(int i = 0;i < s.size();i++)
{
c = s[i];
if(c != '[' && c != ']')
{
if(op == 1)
l.push_back(c);
else
{
it = l.insert(it,c);
it++;
}
}
else if(c == '[')
{
op = -1;
it = l.begin();
}
else
{
op = 1;
it = l.end();
}
}
for(list<char>::iterator it = l.begin();it != l.end();it++)
{
cout << *it;
}
return 0;
}
