字符串解码（猿辅导笔试题数箱子）

可以申请两个栈，一个存放数字一个存放字符。本题我们直接申请一个栈，数据类型设定为pair<int,string>。遍历原字符串时，遇到数字则计算保存到num中，遇到左括号 [ 则入栈，入栈后，将num置0，将字符串清空；遇到字符则进行拼接保存至res中，遇到右括号 ] 则出栈。在出栈时，首先得到栈顶数字n，然后得到栈顶字符串str，拼接的重复次数为栈顶数字指定的大小，拼接的方式为str=str+res。

代码如下：

class Solution {
public:
    string decodeString(string s) {
        stack<pair<int,string>>st;
        string res="";
        int num=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]-0>=0&&s[i]-0<=9){
                num*=10;
                num+=s[i]-0;
            }
            else if(s[i]==[){
                st.push(make_pair(num,res));
                num=0;
                res="";
            }
            else if(s[i]==]){
                int n=st.top().first;
                string str=st.top().second;
                st.pop();
                for(int j=0;j<n;j++)
                    str=str+res;     //字符串重复多次，多次拼接
                res=str;
            }
            else
                res+=s[i];
        }
        return res;
    }
};

做完字符串解码后，看猿辅导的一道笔试题，题目的具体故事背景记不清了，大概问题是： 输入一个只包含 [ 、] 、数字(1-9)的字符串。[ ]表示一个箱子，[ ]3表示3个箱子，[ ]内部可以嵌套更多的箱子，即大箱子装小箱子。求字符串最终对应的箱子数量。 比如：[ ] [ [ ] [ ] [ ]2 ]3 表示 1+(1+1+2)*3+3=16，则最终的箱子数为16。

这道题就类似于字符串解码，当然也可以用递归的方法做（可以自己尝试，相比较于字符串解码的思想要复杂一点），分析这道题，首先我们从后向前看，对于遇到的字符，如果是数字，首先箱子总数要加上该数字num。然后若这个数字接下来对应的箱子中有嵌套箱子，则需要用该数字乘以嵌套中的箱子数量，遍历完当前的最外层箱子，接下来就是判断前面是否还有大箱子，有则加上该箱子的总数。

我们用栈来做：首先遇到数字，我们保存至num中（注意num初始化为1，因为没有数字默认为1），然后遇到 ] 时，我们将num入栈，然后将num置1，遇到 [ 则出栈，获取栈顶数字n，然后判断此时栈是否为空，不为空，则说明我们还在计算某个大箱子内嵌套的箱子总数，则temp+=n;为空则说明我们遍历完一个完整的大箱子了，此时总数res+=n*temp+n;然后将temp置0，方便接下来继续遍历计算。结合代码看就会明白计算规则。

代码如下：

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int res = 0;
void track(string s)
{
    stack<int>st;
    int num = 1;
    int temp = 0;
    for (int i = s.size() - 1; i >= 0; i--)
    {
        if (s[i] - 0 >= 0 && s[i] - 0 <= 9) {
            num = s[i] - 0;
        }
        else if (s[i] == ]) {
            st.push(num);
            num = 1;
        }
        else if (s[i] == [) {
            int n = st.top();
            st.pop();
            if (st.empty())
            {
                res += n * temp + n;   //外层箱子数为n，内部装的箱子数为temp
                temp = 0;              //置0方便计算接下来遇到新的含嵌套的箱子
            }
            else
                temp += n;        //计算含嵌套的箱子中装了多少个箱子
        }
    }
}
int main() {
    string s;
    cin >> s;
    track(s);
    cout << res << endl;
    return 0;
}