昨天面试被要求敲这个代码。。
问题描述:
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: [k|encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例输入:AB[2|BC[2|CD]]AB
示例输出:ABBCCDCDBCCDCDAB
思路:栈迭代
面试过程中被看着写代码真的太难了,虽然有思路,但是细节处理的很不好,最后出错了,数组越界,代码太烂了。。。
事后补上。。。
#include <iostream> #include <string> #include <vector> #include<algorithm> using namespace std; string getDigits(string &s, int &ptr){ string ret = ""; while (isdigit(s[ptr])){ ret.push_back(s[ptr++]); } return ret; } string getString(vector<string> &sub){ string ret = ""; for(auto s : sub){ ret +=s; } return ret; } int main() { string str; cin>>str; vector<string> stk; int ptr = 0; while(ptr < str.size()){ char ch = str[ptr]; if (isdigit(ch)) { string digits = getDigits(str, ptr); stk.push_back(digits); } else if (isalpha(ch) || ch == '[' || ch == '|'){ stk.push_back(string(1, str[ptr++]));//char转为string,构造函数string (size_t n, char c); } else { ++ptr; vector<string> sub; while(stk.back() != "|") { sub.push_back(stk.back()); stk.pop_back(); } reverse(sub.begin(), sub.end()); stk.pop_back();//"|"出栈 int repTime = stoi(stk.back());//字符串转数字,非数字会报错 stk.pop_back();//数字出栈 stk.pop_back();//左括号出栈 string t, o=getString(sub); while(repTime){ t += o; repTime--; } stk.push_back(t); } } cout<<getString(stk) <<endl; return 0; }