华为笔试题。将括号里的内容按一定规则展开,感觉考查字符串处理和栈的使用。
题目
题目描述
给定一个字符串,字符串包含数字、大小写字母以及括号(包括大括号、中括号和小括号),括号可以嵌套,即括号里面可以出现数字和括号。按照如下的规则对字符串进行展开,不需要考虑括号成对不匹配的问题,用例保证括号匹配,同时用例保证每个数字后面都有括号,不用考虑数字后面没有括号这种情况,即2a2(b)这种情况不用考虑。
- 数字表示括号里的字符串重复的次数,展开后的字符串不包含括号。
- 将字符串进行逆序展开。
输出最终展开的字符串。
输入描述
输入一个长度小于100的字符串。
输出描述
输出展开后的字符串。
示例1
输入输出示例仅供调试,后台判题数据一般不包含示例
输入
abc3(A)
输出
AAAcba
分析
这题是字符串展开问题,如果括号里只有一个纯字符串不难,只需要将括号里的字符串复制指定次数再放进去就好了。但是难就难就在,如果括号里的字符串还有括号怎么办,递归处理也是一种思路。我的思路是从左向右扫描,当第一次遇到右括号时,比如)、]、}这三个,这个括号里的字符串一定是一个不包含括号的字符串,否则这就不是我遇到的第一个右括号,然后展开,继续扫描即可。
代码
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
| #include <iostream> #include <vector> #include <string> #include <stack> using namespace std;
class Solution { public: string f(string input_str) { stack<char> result; stack<char> kuohao; string result_str; for (char c : input_str) { if (c != ')' && c != ']' && c != '}') { result.push(c); } else { char left_kh; if (c == ')') { left_kh = '('; } else if (c == ']') { left_kh = '['; } else { left_kh = '{'; } vector<char> tmp; while (result.top() != left_kh) { tmp.push_back(result.top()); result.pop(); } result.pop(); int tmp_count = 0; while (result.top() >= '0' && result.top() <= '9') { tmp_count *= 10; tmp_count += (result.top() - '0'); result.pop(); } for (int i = 0; i < tmp_count; i++) { for (auto it = tmp.rbegin(); it != tmp.rend(); it++) { result.push(*it); } } tmp.clear(); } } while (!result.empty()) { result_str += result.top(); result.pop(); } return result_str; } };
int main() { string str = "abc3[ABC9(kjh6{rtf}zxc)asd]"; Solution s; cout << s.f(str) << endl; return 0; }
|