使用Stack（栈）解决Alice图书馆重排问题出错，DSA入门者求助

现有代码错误点 #

• 索引越界：循环范围写了range(len(x)+1)，输入列表x的合法索引范围是0 ~ len(x)-1，遍历到len(x)时会直接触发索引超出范围的报错。
• 栈访问逻辑错误：处理右隔板\时，用输入字符串的索引i访问栈self.s[i]完全不符合逻辑，应该判断栈顶元素是否为左隔板/。
• 流程逻辑错误：遇到第一个右隔板就直接返回结果，只能处理一层嵌套，无法处理多层隔板的反转需求，且反转后的内容没有重新压回栈中参与外层的反转操作，左隔板也没有弹出销毁。
• 边界判断顺序错误：while循环中先判断栈元素再判断栈是否为空，空栈时访问元素会触发报错，应该先判断栈非空再取元素。

正确实现思路 #

用栈处理的核心逻辑：

• 遍历输入的每个字符，所有字符除了右隔板\都直接压入栈
• 遇到右隔板\时，不断弹出栈顶元素，直到弹出左隔板/为止，弹出的中间字符就是当前最内层书架的书籍，顺序已经是反转后的（栈后进先出的特性天然实现反转）
• 把反转后的这些书籍字符重新压入栈，继续遍历后续字符
• 遍历完成后，栈中剩余的所有字符拼接就是最终结果

修改后的代码 #

class Stack:
    def __init__(self):
        self.s = []
    
    def lib(self, x):
        for char in x:
            if char != '\\':
                self.s.append(char)
            else:
                # 弹出到左隔板为止，收集当前层书籍
                temp = []
                while self.s and self.s[-1] != '/':
                    temp.append(self.s.pop())
                # 弹出左隔板销毁
                if self.s:
                    self.s.pop()
                # 反转后的当前层书籍重新压入栈，参与外层处理
                self.s.extend(temp)
        # 拼接栈内所有字符得到最终结果
        return ''.join(self.s)

if __name__ == '__main__':
    x = "/u/love\\i\\"
    d = Stack()
    print(d.lib(x))

运行验证 #

输入样例/u/love\i\，运行后输出iloveu，和样例输出一致。

内容的提问来源于stack exchange，提问作者Yin Yu