有了防护伞，并不能完全避免 2012 的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力，小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码，才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码，外星人对于连续的若干个相同的子串“X”会压缩为“[DX]”的形式（DD 是一个整 数且 1≤D≤991≤D≤99），比如说字符串“CBCBCBCB”就压缩为“[4CB]”或者“[2[2CB]]”，类似于后面这种压缩之后再压缩的称为二重压缩。如果是“[2[2[2CB]]]”则是三重的。现在我们给你外星人发送的密码，请你对其进行解压缩。

输入格式

第一行：一个字符串。

输出格式

第一行：一个字符串。

输入输出样例

输入 #1

1
AC[3FUN]

输出 #1

1
ACFUNFUNFUN

说明/提示

【数据范围】
对于 50%50\% 的数据：解压后的字符串长度在 10001000 以内，最多只有三重压缩。
对于 100%100\% 的数据：解压后的字符串长度在 2000020000 以内，最多只有十重压缩。 对于 100%100\% 的数据：保证只包含数字、大写字母、’[‘和’]‘。

思路

密码的解压缩总是从最里面一层开始，然后逐层往上解压，逐层返回，很容易想到用递归解题。
如果读到左中括号，则进入递归，对下一层进行解压，直到碰到右中括号，返回当前解压的字符串，遇到右括号时再向上一层返回。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<string>
using namespace std;
string ans() {
	int n;
	char c;
	string s;
	while (cin >> c) {
		if (c == '[') {
			cin >> n;
			//下一层递归
			string temp = ans();
			while (n--) {
				s += temp;
			}
		} else {
			if (c == ']') {
				//返回字符串
				return s;
			} else {
				s += c;
			}
		}
	}
}
int main() {
	cout << ans() << endl;
	return 0;
}