字元串解碼（猿輔導筆試題數箱子）

可以申請兩個棧，一個存放數字一個存放字元。本題我們直接申請一個棧，資料類型設定為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;
}