题目简介：
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:
1
2
3
| s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
|
思路：
利用栈，遇到数字时则将连续的一串数字压入栈(如326[a]，遇到3时，将326找到并作为整体压入栈)；
遇到字母或左括号时直接压入栈；
遇到右括号时开始弹出栈顶元素，直到遇到左括号为止，则中间弹出的均是字母，将这些字母保存起来并翻转到正确的顺序。将左括号弹出后，此时栈顶元素为数字，将数字弹出，并根据数字生成新的字符串并压入栈。
最后栈中只会有一系列的字符串，获取后翻转至正确顺序，组合起来返回即可。
tips:
- 判定字符是否是数字是可用
isdigit()函数，判定字符是否是字母时可用isalpha()函数。
- 字符串转换为数字时可用
stoi()函数。
char转换为string类型时，可用string (size_t n, char c), 如string(1, 'c')。
代码如下：
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
| class Solution {
public:
string getdigits(string s, int& ptr){
string res = "";
while(isdigit(s[ptr])){
res += s[ptr++];
}
return res;
}
string getstring(vector<string> in_str){
string res = "";
for(auto s : in_str){
res += s;
}
return res;
}
string decodeString(string s) {
stack<string> temp;
int i = 0;
while(i < s.length()){
if(isdigit(s[i])){
string num = getdigits(s, i);
temp.push(num);
}
else if(isalpha(s[i]) || s[i] == '['){
temp.push(string(1, s[i]));
i++;
}
else{
i++;
vector<string> sub;
while(temp.top() != "["){
sub.push_back(temp.top());
temp.pop();
}
temp.pop();
int time = stoi(temp.top());
temp.pop();
reverse(sub.begin(), sub.end());
string sub_str, time_str = getstring(sub);
while(time != 0){
sub_str += time_str;
time--;
}
temp.push(sub_str);
}
}
vector<string> res;
while(!temp.empty()){
res.push_back(temp.top());
temp.pop();
}
reverse(res.begin(), res.end());
return getstring(res);
}
};
|
