HDOJ 1274 展开字符串

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1274

一个关于字符串处理的题目，因为有括号，如果每一次都是去找最里面的左括号再找对应右括号肯定不好处理，我们采取的方法就是直接从左到右的处理，然后遇到括号我们就采取递归的思想去处理，因为涉及到字符串的拼接，所以这里我们最好用到的C++ string类型，虽然慢但是还是比较好用的。

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000+5;
char str[maxn];
bool vis[maxn];
int len;
string dfs(int pos)
{
string ans = "", tmp = "", tmp2 = "";
int num = 0;
for(int i=pos; i<=len; i++)
{
if(vis[i]) continue;
vis[i] = 1;
if((str[i] >= '0' && str[i] <= '9'))
num = num*10 + str[i] - '0';
else if(str[i] >= 'a' && str[i] <= 'z')
{
if(num == 0) num = 1;
for(int j=0; j<num; j++)
tmp += str[i];
num = 0;
}
if(str[i] == '(')
{
ans += tmp;
tmp2 = dfs(i+1);
if(num == 0) num = 1;
for(int j=0; j<num; j++) ans += tmp2;
tmp = "";
num = 0;
}
if(str[i] == ')')
{
ans += tmp;
return ans;
}
}
ans += tmp;
return ans;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
memset(vis, 0, sizeof(vis));
scanf("%s", str);
len = strlen(str);
string ans = dfs(0);
cout << ans << endl;
}
}