[leetcode]394.文字列復号

符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、k[encoded_string]であり、カッコ内のencoded_を表すstringはちょうどk回繰り返します.注意kは正の整数であることを保証する.
入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.
また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.
例:

s = "3[a]2[bc]",   "aaabcbc".
s = "3[a2[c]]",   "accaccacc".
s = "2[abc]3[cd]ef",   "abcabccdcdcdef".

構想:補助スタックstackを構築し、文字列s中の各文字cを遍歴する.1.cが数字である場合、数字文字を数字multiに変換し、後続の倍数計算に用いる.2.cがアルファベットである場合、resの末尾にcを追加する.3.cが‘‘‘‘‘である場合、現在のmultiとresをスタックに入れ、それぞれ0.1を空けておく)この‘‘‘‘‘の前の一時結果resをスタックに記録し、対応する’を発見した後の接合操作;2)この‘‘‘‘‘‘’の前の倍数multiをスタックに記録し、対応を発見するために用いる’を記録した後、multiを取得する× [...]文字列.3)新しい'['に入ると、resとmultiが再記録されます.cが']の場合、stackはスタックを出て、文字列res=last_res + cur_Multi*res、そのうち:last_resは、前の[現在の[文字列、例えば「3[a 2[c]」のaである.cur_Multiは、「3[a 2[c]」の2のような現在の[から]内文字列の繰返し倍数である.文字列resを返す
例えば3[a 2[c],アルゴリズムプロセス:1.まずresが空で、最初の文字が3であればrepeatTime=3、さらに後ろに'[]となり、そこでスタックに入る(3,""").同時に、resが空で、repeatTimesが0.2.aを遍歴する.3.2まで遍歴し、repeatTime=2.4.まで遍歴し、'['、スタックに入る(2,"a")、同時に、resが空で、repeatTimesが0.5.cまで遍歴するするとres="a"+res 2=acc.となる.'''''に遍歴し、スタックを出て、スタックトップ要素が(3,"")、res="+res 3=accaccac 8.はresを返します.
ACコード:(C++)

class Solution {
   public:
    string repeat(const string& str, int times) {
        // str times 
        string res = "";
        for (int i = 0; i < times; i++) {
            res += str;
        }
        return res;
    }
    string decodeString(string s) {
        int repeatTimes = 0;
        string res = "";
        stack<pair<int, string>> vecStack;
        for (char i : s) {
            if (i >= '0' && i <= '9')
                repeatTimes = (repeatTimes * 10) + (i - '0');
            else if (i == '[') {
                vecStack.push(make_pair(repeatTimes, res));
                res = "";
                repeatTimes = 0;
            } else if (i == ']') {
                pair<int, string> temp = vecStack.top();
                vecStack.pop();
                res = temp.second + (temp.first == 0 ? "" : repeat(res, temp.first));
            } else
                res += i;
        }
        return res;
    }
};