Former Coding Interview Question: Compression and Decompression

問題. Compression and Decompression

小文字のアルファベットからなる文字列をある規則（ここを参照）で圧縮したものが与えられるので復元せよ．

解法

与えられた文字列の現在見ている要素のイテレータ begin と最後尾要素の次を指すイテレータ end を引数として渡して再帰関数で求めた．与えれた文字列に含まれない文字を末尾に加えて end を引数から削除した再帰も考えられるがどちらが良いのだろう．

計算時間： （ は文字列の長さ）

ソースコードを表示

#include <iostream>

std::string Recursive(std::string::const_iterator &begin, const std::string::const_iterator end) {
    std::string res;

    while (begin != end && *begin != ']') {
        if (std::isalpha(*begin)) {
            res += *begin;
            ++begin;
        }
        else if (std::isdigit(*begin)) {
            int num = 0;
            while (begin != end && std::isdigit(*begin)) {
                num = (10 * num) + (int)(*begin - '0');
                ++begin;
            }
            ++begin;
            std::string add_string = Recursive(begin, end);
            for (int i = 0; i < num; ++i) res += add_string;
            ++begin;
        }
        else if (*begin == '[') {
            ++begin;
            Recursive(begin, end);
            ++begin;
        }
    }

    return res;
}

inline std::string Decompress(const std::string &s) {
    std::string::const_iterator begin = s.begin();
    return Recursive(begin, s.end());
}

int main() {
    std::cin.tie(0); std::ios::sync_with_stdio(false);

    for (std::string s; std::cin >> s; ) {
        std::cout << s << " -> " << Decompress(s) << std::endl;
    }

    return 0;
}

問題の説明がややこしいので省略．
もっとシンプルに書けるものなのかな．