leetcode/394_decode_string.cpp at main · cotoirares/leetcode · GitHub

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Solution {
public:
    bool integer(char c){
        return c >= '0' && c <= '9';
    }

    int get_factor(string factor){
        int number = 0;
        reverse(factor.begin(), factor.end());
        for (char c : factor) {
            number = number * 10 + (c - '0');
        }
        return number;
    }

    string decodeString(string s) {
        stack<char> st;
        int open_brack = 0;
        string result = "";
        string curr_string = "";
        for (char c: s){
            if (open_brack == 0 && integer(c)){
                if (!curr_string.empty()) {
                    result += curr_string;
                    curr_string = "";
                }
            }
            if (open_brack == 0 && !integer(c) && c != '[' && c != ']') {
                curr_string += c;
                continue;
            }
            if (c == '[') {
                open_brack++;
                st.push(c);
            }
            else if (c == ']'){
                open_brack--;
                string factor="", aux="";
                if (open_brack == 0){
                    while (!st.empty() && st.top()!='[') {
                        aux += st.top();
                        st.pop();
                    }
                    st.pop(); // Pop the '['
                    while (!st.empty() && integer(st.top())){
                        factor += st.top();
                        st.pop();
                    }
                    int mul_factor = get_factor(factor);
                    reverse(aux.begin(), aux.end());
                    string temp = "";
                    while (mul_factor--)
                        temp += aux;
                    result += temp;
                }
                else{
                    while (!st.empty() && st.top()!='[') {
                        aux += st.top();
                        st.pop();
                    }
                    st.pop(); // Pop the '['
                    while (!st.empty() && integer(st.top())){
                        factor += st.top();
                        st.pop();
                    }
                    int mul_factor = get_factor(factor);
                    reverse(aux.begin(), aux.end());
                    string temp = "";
                    while (mul_factor--) {
                        temp += aux;
                    }
                    for (char x : temp)
                        st.push(x);
                }
            }
            else {
                st.push(c);
            }
        }
        if (!curr_string.empty()) {
            result += curr_string;
        }
        string aux="";
        while (!st.empty()) {
            aux += st.top();
            st.pop();
        }
        if (!aux.empty()) {
            reverse(aux.begin(), aux.end());
            result += aux;
        }
        return result;
    }
};