LeetCode 字符串解码堆栈应用算法

背景：数据结构中的堆栈在以往的工作和学校里都没有怎么用过，但是这个算法如果在需要的场合中使用能够发挥非常大的作用，下面是一个LeetCode中的题目和解法。
题目：
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:

s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef"

解析：
需要从最深的括号入手进行构造，逐层向上拼接并继续构造，最终组合成字符串。考虑到堆栈的特性是后来先处理，因此用堆栈实现任务记录，然后就能从最深的任务开始执行并向上递归，最终实现构造。
【LeetCode 字符串解码堆栈应用】以"a3[b4[df]]f2[cv]"为例进行分析：
首先是处理"4[df]"然后是和"b"拼接，然后构造后拼接a，再拼接后边的模块。
方法是，遇到'['就执行一次压栈，然后遇到']'就进行一次出栈构造，拼接不需要多重构造的字符串，继续流程

class Solution: def decodeString(self, s): """ :type s: str :rtype: str """ tempIntStr = '' tempStr = '' tempIntStack = [] tempStrStack = []reStr = '' bisn = Falsefor c in s: if c.isnumeric() and bisn: tempIntStr += c elif c == '[': tempIntStack.insert(0, tempIntStr) tempIntStr = '' tempStrStack.insert(0, '') bisn = False elif c == ']':if len(tempStr) > 0: tempStrStack[0] = tempStrStack[0] + tempStr tempStr = '' ts = tempStrStack[0] del tempStrStack[0] ti = int(tempIntStack[0]) del tempIntStack[0] tss = '' for i in range(ti): tss += ts if len(tempStrStack) == 0: reStr += tss else: tempStrStack[0] = tempStrStack[0] + tsselif c.isnumeric() and not bisn: tempIntStr += c if len(tempIntStack) == 0: reStr += tempStr else: tempStrStack[0] = tempStrStack[0] + tempStr tempStr = '' bisn = True else: tempStr += c reStr += tempStr return reStr

这个算法能实现O(n)的时间复杂度，还是能够满足题目的要求的。