394.字符串解码题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/decode-string题目给定一个编码后的字符串，返回它对字符串进行解码。编码规则为：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”。解题思路：Stack在上面的例子中，第二个例子有一种情况是嵌套括号。在本题中，也是这部分比较难处理。在这篇文章中，我们使用栈的思想来解决这个问题。上面提到的嵌入括号的情况，我们在返回的时候，需要从里到外生成并拼接字符，这也是我们使用栈的原因，因为栈具有先进后出的特点。这里，在我们的栈中，每一项需要存储两条信息，一条是左括号前的字符，一条是左括号前的数字。比如例2、3[a2[c]]，a2[c]部分入栈时应该是这样的：('a',2)，后面会遍历字符c。当遇到右括号时，应该执行入栈操作。弹出元素('a',2)，这里需要和字符c拼接，形成新的字符串a+2*'c'，即acc。具体方法：当遍历元素为数字时，将数字字符转换为数字，用于后续的字符解码乘数操作；当遍历元素为字母时，此时直接将该字符添加到结果的末尾；将左括号前面的字母和数字入栈，入栈后，重新设置存放这两项的变量；当遍历元素为右括号时，出栈并拼接字符。算法实现过程图如下：具体代码实现如下。代码实现类解决方案：defdecodeString(self,s:str)->str:#辅助栈，每一项存储两条信息，左括号前一个字符，左括号前一个数字stack=[]mult=0ans=''forcharins:#当字符为数字字符时，转为值进行后续多次运算ifchar.isdigit():#mult=int(char)#注意位数这里，#上面的写法，我在用例“100[leetcode]”中遇到了错误，这里改为mult=mult*10+int(char)#遇到左括号时，压入前一个字符和值入栈elifchar=='[':stack.append((ans,mult))#这里存储这两项的变量要被重置ans=''mult=0#当遇到右括号时,出栈elifchar==']':front_char,cur_mult=stack.pop()ans=front_char+cur_mult*ans#这里表示遇到的是一个字符，directly加在anselse的末尾：ans+=charreturnans实现结果总结这道题比较难的问题是内嵌括号的问题，这里要从里向外展开，这样符合先进后出的原则out栈的特性，所以用栈的思想来解决这个问题。建立一个辅助栈，每一项存储两条信息，左括号前的字符，左括号前的值来遍历字符串，分别处理不同的情况：当遍历的元素是数字字符时，进行转换toavalueforSubsequentmultiplecalculations（这里要注意位数，不一定只有个位数）。当遍历元素为字母时，将其添加到结果的末尾。在堆栈中，同时重置存储这两项的变量。当遍历元素为右括号时，开始出栈，同时拼接字符。欢迎关注微信公众号《书所集录》
