394. Decode String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

struct Data {
    string s;
    int rep;

    Data(string _s, int _rep)
    {
        s = _s;
        rep = _rep;
    }
};

class Solution
{
public:
    string decodeString(string s)
    {
        stack<Data> st;

        string tmp = "";
        int rep = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            // printf("%d\n", i);

            if (s[i] == '[') {
                st.push(Data("", rep));
                rep = 0;
                continue;
            } else if (s[i] == ']') {
                if (tmp.size() > 0) {
                    st.push(Data(tmp, -1));
                    tmp = "";
                }

                Data d("", -1);
                string concat = "";
                while (1) {
                    d = st.top();
                    st.pop();
                    // printf("%s %d\n", d.s.c_str(), d.rep);

                    if (d.rep != -1)
                        break;
                    concat = d.s + concat;
                }

                string ntmp = "";
                for (int j = 0; j < d.rep; j++)
                    ntmp += tmp.size() > 0 ? tmp : concat;

                st.push(Data(ntmp, -1));
            } else if ('0' <= s[i] && s[i] <= '9') {
                if (tmp.size() > 0) {
                    st.push(Data(tmp, -1));
                    tmp = "";
                }

                rep *= 10;
                rep += s[i] - '0';
            } else { // letters
                tmp += s[i];
            }
        }

        if (tmp.size() > 0)
            st.push(Data(tmp, -1));

        string ans = "";
        while (st.size() > 0) {
            Data d = st.top();
            st.pop();

            ans = d.s + ans;
        }

        return ans;
    }
};