问题描述：Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.
样例
s = abc3[a] return abcaaa s = 3[abc] return abcabcabc s = 4[ac]dy, return acacacacdy s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz
问题需要维护两个栈，一个数字栈一个字符栈。同时遇到“20[ab]时，这里的数字是20，避免取错。这里主要是当遇到 ']’ 时，需要将在数字栈中将数字取出，同时把相应的字符在字符栈中取出。将字符转换为string的话，用stringstream进行转换。具体代码如下：class Solution { public: /** * @param s an expression includes numbers, letters and brackets * @return a string */ string expressionExpand(string& s) { // Write your code here int length = s.size(); stack<int> s_numbers; stack<char> s_chars; int save_num = 0; for(int i = 0;i!=length;++i){ if(isNumber(s[i])){ save_num = save_num*10+s[i]-'0'; continue; } else if(s[i]=='['){ s_numbers.push(save_num); save_num = 0;//计数重新清零 s_chars.push(s[i]); } else if(s[i]==']'){ int times = s_numbers.top(); s_numbers.pop(); vector<char> temp_chars; while(s_chars.top()!='['){ temp_chars.push_back(s_chars.top()); s_chars.pop(); } //弹出[] s_chars.pop(); for(int time=1;time<=times;++time){ for(int i = temp_chars.size()-1;i>=0;--i){ s_chars.push(temp_chars[i]); } } } else{ s_chars.push(s[i]); } } //输出栈中的元素 string res; stack<char> temp_char; stringstream ss; int stack_size = s_chars.size(); for (int i = 0; i != stack_size; ++i){ temp_char.push(s_chars.top()); s_chars.pop(); } for (int i = 0; i != stack_size; ++i){ ss << temp_char.top(); temp_char.pop(); } ss >> res; return res; } bool isNumber(char c){ int flag = c - '0'; return flag >= 0 && flag <= 9; } };
