数箱子:
[]表示一个箱子
[]3表示三个箱子,
[[]3]2,表示有两个大箱子,每个箱子里放了三个小箱子,总共八个箱子。
给一段字符串判断里面有多少箱子
此题情况复杂,可能会出现[[]3[[]2]2]3
这种多种嵌套情况。
本题思路采取递归。
得到字符串后先遍历字符串,将字符串拆成并列的几个字符串,
例如:[[]3[[]2]2]3
内部的 []3[[]2]2
需要拆成 []3
与 [[]2]2
设函数 fun(string a, int mut)
假设初始问题为 fun("[]2[[]3]2", 1)
, 则将其转化为 1 + fun("[]2", 2) + fun("[[]3]2", 2)
递归出口则是字符串参数为空,返回mut
. 例如 []3
相当于 fun("", 3)
返回 3.
得到字符串a
时,直接调用函数fun(a,1)-1
即可。由于这样调用相当于外层多套了单个大箱子,故答案减一.
代码如下(测试用例不足,故不一定完全正确):
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int help(string a, int mut){
//cout << "调试:" << a << " " << mut << endl;
int n = a.length();
if(n == 0) return mut;
int res = mut;
int cnt = 0;
for (int i = 0, j = 0; i < n; i ++ )
{
if(a[i] == '[') cnt ++;
else if(a[i] == ']') cnt --;
if(a[i] == ']' && cnt == 0)
{
int t = 1;
if(i+1 < n && a[i+1] >= '1' && a[i+1] <= '9')
{
t = a[i+1] - '0';
}
res += help(a.substr(j+1, i-j-1), mut * t);
j = i+1;
if(i+1 < n && a[i+1] >= '1' && a[i+1] <= '9')
{
j++;
}
}
}
return res;
}
int main()
{
string a;
cin >> a;
cout << help(a, 1) - 1 << endl;
return 0;
}