Python 알고리즘 응용 실무 스택

스택이란? 제한된 작업을 수행하는 선형 테이블인 선입후출(First In Last Out) 데이터 구조로 이해할 수 있습니다. 다음 글은 주로 파이썬에서 스택을 실제로 적용하는 방법을 소개합니다. 도움이 필요한 친구들이 함께 참고해 보세요.

stack

스택은 스택이라고도 합니다. 삽입 및 삭제 작업은 스택의 맨 위에서 수행되며 선입, 후-의 규칙에 따라 수행됩니다. 아웃 및 후입선출 작업.

아래 그림과 같이

예를 들어 총의 탄창에서는 탄창에 처음으로 넣은 총알이 발사될 때 마지막 총알이 되고 탄창에 마지막으로 넣은 총알은 발사되었을 때 처음으로 발사되었습니다.

스택 인터페이스

스택을 생성하는 경우 스택을 작동하려면 다음과 같은 인터페이스가 있어야 합니다. )

스택으로 푸시

s = []

Create a stack

# 创建一个栈
In [1]: s = []
# 往栈内添加一个元素
In [2]: s.append(1)
In [3]: s
Out[3]: [1]
# 删除栈内的一个元素
In [4]: s.pop()
Out[4]: 1
In [5]: s
Out[5]: []
# 判断栈是否为空
In [6]: not s
Out[6]: True
In [7]: s.append(1)
In [8]: not s
Out[8]: False
# 获取栈内元素的数量
In [9]: len(s)
Out[9]: 1
In [10]: s.append(2)
In [11]: s.append(3)
# 取栈顶的元素
In [12]: s[-1]
Out[12]: 3

스택의 기본 개념을 이해한 후 이해를 돕기 위해 몇 가지 예제를 더 살펴보겠습니다. 괄호 일치

Question

표현식에 세 개의 대괄호(), [], {}가 포함될 수 있는 경우 중첩 순서는 임의적입니다. 예:

올바른 형식

{()[()]},[{({})}]

잘못된 형식

[(]),[()),(()}

표현식 문자열의 대괄호 일치가 올바른지 확인하는 함수를 작성하세요

Idea

빈 스택을 만들어 아직 찾지 못한 왼쪽 대괄호를 저장하세요.

편의 문자열은 왼쪽 대괄호를 만나면 스택에 푸시되고, 오른쪽 대괄호를 만나면 일치를 위해 왼쪽 대괄호가 스택에서 튀어나옵니다.

두 번째 단계에서 오른쪽 대괄호가 나오면 스택이 비어 있을 때 대괄호가 발생하면 왼쪽 대괄호가 누락되었음을 의미합니다.

순회 두 번째 단계가 끝나면 스택이 비어 있지 않아 오른쪽 괄호가 누락되었음을 나타냅니다.

1. 코드 해결 방법

더 나은 편의를 위해 pycharm에서 점을 나누는 것이 좋습니다.

2. #!/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(&#39;[(){()}]&#39;)
   print(result)

   로그인 후 복사

3. 미로 문제를 이해하려면

4. Question

2차원 배열을 사용하세요. 간단한 미로를 표현하려면 0을 사용하여 통로를 나타내고 1을 사용하여 블록을 나타냅니다. 마우스는 각 지점에서 인접하게 이동할 수 있습니다. 남동쪽, 북서쪽, 북서쪽의 네 지점을 사용하여 마우스가 미로를 통과하는 것을 시뮬레이션하는 알고리즘을 설계합니다. 미로를 찾아 입구에서 출구까지의 경로를 찾으세요.

사진과 같이

근처에 있는 4개의 지점 중 도달 가능한 지점 중 하나를 선택하세요.

특정 지점에 도달한 후 근처 4개 지점으로 이동하지 않으면 이때 막다른 골목에 도달했다는 의미입니다. 다른 점을 시도하십시오. 컴파일러는 일반적으로 괄호가 필요 없는 후위 표현식을 사용합니다.

2. 중위 표현식

후위 표현식

4. 2 + 3 * 4

2 3 4 *
5. ( 1 + 2 ) * ( 6 / 3 ) + 2
   1 2 + 6 3 / * 2 +

编写程序实现后缀表达式求值函数。

思路

1. 建立一个栈来存储待计算的操作数；

2. 遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算

3. 按上述过程，遍历完整个表达式，栈中只剩下最终结果；
   

解决代码

#!/use/bin/env python
# _*_ coding:utf-8 _*_
operators = { # 运算符操作表
 '+': lambda op1, op2: op1 + op2,
 '-': lambda op1, op2: op1 - op2,
 '*': lambda op1, op2: op1 * op2,
 '/': lambda op1, op2: op1 / op2,
}
def evalPostfix(e):
 """
 :param e: 后缀表达式
 :return: 正常情况下栈内的第一个元素就是计算好之后的值
 """
 tokens = e.split() # 把传过来的后缀表达式切分成列表
 stack = []
 for token in tokens: # 迭代列表中的元素
 if token.isdigit(): # 如果当前元素是数字
  stack.append(int(token)) # 就追加到栈里边
 elif token in operators.keys(): # 如果当前元素是操作符
  f = operators[token] # 获取运算符操作表中对应的lambda表达式
  op2 = stack.pop() # 根据先进后出的原则，先让第二个元素出栈
  op1 = stack.pop() # 在让第一个元素出栈
  stack.append(f(op1, op2)) # 把计算的结果在放入到栈内
 return stack.pop() # 返回栈内的第一个元素
result = evalPostfix('2 3 4 * +')
print(result)
# 14

背包问题

题目

有一个背包能装10kg的物品，现在有6件物品分别为：

编写找出所有能将背包装满的解，如物品1+物品5。

解决代码

#!/use/bin/env python
# _*_ coding:utf-8 _*_
def knapsack(t, w):
 """
 :param t: 背包总容量
 :param w: 物品重量列表
 :return:
 """
 n = len(w) # 可选的物品数量
 stack = [] # 创建一个栈
 k = 0 # 当前所选择的物品游标
 while stack or k < n: # 栈不为空或者k<n
 while t > 0 and k < n: # 还有剩余空间并且有物品可装
  if t >= w[k]: # 剩余空间大于等于当前物品重量
  stack.append(k) # 把物品装备背包
  t -= w[k] # 背包空间减少
  k += 1 # 继续向后找
 if t == 0: # 找到了解
  print(stack)
 # 回退过程
 k = stack.pop() # 把最后一个物品拿出来
 t += w[k] # 背包总容量加上w[k]
 k += 1 # 装入下一个物品
knapsack(10, [1, 8, 4, 3, 5, 2])
"""
[0, 2, 3, 5]
[0, 2, 4]
[1, 5]
[3, 4, 5]
"""