解压字符串---一道刷过就忘了的题。。。

昨天面试被要求敲这个代码。。

问题描述:

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: [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;
}

 

上一篇:Evaluate Reverse Polish Notation


下一篇:SysTick(系统定时器)