394. 字符串解码

394. 字符串解码

给定一个经过编码的字符串,返回它解码后的字符串
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

解题思路:

用栈保存字符,遇到右括号停止,将与它对应的左括号之间的字符进行解码,然后压栈;如此循环,直到解完为止。

没有考虑到的点:

1、数字可能是多位的,例如:“100[leetcode]”;
2、取栈顶的时候注意栈是否为空,否则会溢出;
3、栈是反顺序,需要时刻关注取出的字符串的顺序;

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
string decodeString(string s) {
    string res;
    if(s.empty())
        return res;
    stack<char> s1;
    for(auto i:s){
        string tmp;
        if(i == ']'){
            while(s1.top() != '['){
                tmp = s1.top() + tmp;
                s1.pop();
            }
            s1.pop();
            string snum;
            //取数字的时候要关注是否已到栈底
            while(!s1.empty() && isdigit(s1.top())){
                snum += s1.top();
                s1.pop();
            }
            reverse(snum.begin(),snum.end());
            //字符串转数字用stoi函数
            int num = stoi(snum);
            string str;
            while(num > 0){
                str += tmp;
                num--;
            }
            for(auto j:str){
                s1.push(j);
            }
        }else {
            s1.push(i);
        }
    }
    while(!s1.empty()){
        res += s1.top();
        s1.pop();
    }
    reverse(res.begin(),res.end());
    return res;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 4,481评论 0 5
  • 原始值:原始类型的值就是原始值,原始值有string,、number、boolean、null和undefined...
    9372da03c5ef阅读 152评论 0 1
  • #1.第8部分.模块化 ##1.1.什么是模块化 模块化是指在解决某一个复杂问题或者一系列的杂糅问题时,依照一种分...
    敏_程序媛阅读 150评论 0 0
  • 1. 第8部分. 模块化 1.1. 什么是模块化 模块化是指在解决某一个复杂问题或者一系列的杂糅问题时,依照一种分...
    敏_程序媛阅读 276评论 0 0
  • 你以为让女神幻灭的只有衰老吗? 我们先来玩个猜谜游戏吧,来猜猜下面这位是谁? 她!是!许!晴! 没错,就是那个年近...
    伊的家护肤师芬芬阅读 203评论 0 0