「Python 算法实战」：栈

正文

请到「今天看啥」查看全文

编写一个函数，判断一个表达式字符串，括号匹配是否正确

思路

1. 创建一个空栈，用来存储尚未找到的左括号；

2. 便利字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配；

3. 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配；

4. 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配；

解决代码

建议在 pycharm 中打断点，以便于更好的理解

#!/use/bin/env python
# _*_ coding:utf-8 _*_
LEFT = {'(', '[', '{'}  # 左括号
RIGHT = {')', ']', '}'}  # 右括号
def match(expr):
    """
    :param expr:  传过来的字符串
    :return:  返回是否是正确的
    """
    stack = []  # 创建一个栈
    for brackets in expr:  # 迭代传过来的所有字符串
        if brackets in LEFT:  # 如果当前字符在左括号内
            stack




    
.append(brackets)  # 把当前左括号入栈
        elif brackets in RIGHT:  # 如果是右括号
            if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2:
                # 如果当前栈为空，()]
                # 如果右括号减去左括号的值不是小于等于2大于等于1
                return False  # 返回False
            stack.pop()  # 删除左括号
    return not stack  # 如果栈内没有值则返回True，否则返回False
result = match('[(){()}]')
print(result)

迷宫问题

题目

用一个二维数组表示一个简单的迷宫，用0表示通路，用1表示阻断，老鼠在每个点上可以移动相邻的东南西北四个点，设计一个算法，模拟老鼠走迷宫，找到从入口到出口的一条路径。

如图所示

出去的正确线路如图中的红线所示

思路

1. 用一个栈来记录老鼠从入口到出口的路径

2. 走到某点后，将该点左边压栈，并把该点值置为1，表示走过了；

3. 从临近的四个点中可到达的点中任意选取一个，走到该点；

4. 如果在到达某点后临近的4个点都不走，说明已经走入死胡同，此时退栈，退回一步尝试其他点；

5. 反复执行第二、三、四步骤直到找到出口；

解决代码

#!/use/bin/env python
# _*_ coding:utf-8 _*_
def initMaze():
    """
    :return: 初始化迷宫
    """
    maze = [[0] * 7 for _ in range(5 + 2)]  # 用列表解析创建一个7*7的二维数组，为了确保迷宫四周都是墙
    walls = [  # 记录了墙的位置
        (1, 3),
        (2, 1), (2,

请到「今天看啥」查看全文