Python 알고리즘 응용 실무 스택

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

stack

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

아래 그림과 같이

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

스택 인터페이스

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

스택으로 푸시

pop()isEmpty()스택이 비어 있는지 확인스택의 길이를 가져옵니다스택의 맨 위에 있는 요소를 가져오면 요소가 스택에서 튀어나오지 않습니다.스택에 위의 인터페이스가 필요하다는 것을 알고 나면 Python에서 목록은 다음과 유사합니다. 제공되는 인터페이스는 다음과 같습니다. Operation Description

스택에서 팝
	length()
	getTop()

s = []

Create a stack

s.append(x)s.pop() 스택의 요소 삭제스택이 비어 있는지 확인숫자 가져오기 of elements in the stackGet the top of the stackPython의 스택 인터페이스 사용 예:

# 创建一个栈
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

많은 예제

스택에 요소 추가
	s
	len(s)
	s[-1]

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

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을 사용하여 블록을 나타냅니다. 마우스는 각 지점에서 인접하게 이동할 수 있습니다. 남동쪽, 북서쪽, 북서쪽의 네 지점을 사용하여 마우스가 미로를 통과하는 것을 시뮬레이션하는 알고리즘을 설계합니다. 미로를 찾아 입구에서 출구까지의 경로를 찾으세요.

사진과 같이

올바른 나가는 경로는 사진의 빨간색 선으로 표시됩니다

Idea

스택을 사용하여 입구에서 출구까지 마우스의 경로를 기록하세요

특정 지점에 도달한 후 지점의 왼쪽을 스택에 밀어 넣고 지점 값을 1로 설정하여 걸었다는 것을 나타냅니다.

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

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

2. 중위 표현식

후위 표현식

4. 2 + 3 * 4

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

18 / ( 3 * ( 1 + 2 ) )

18 3 1 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件物品分别为：

物品名称	重量
物品0	1kg
物品1	8kg
物品2	4kg
物品3	3kg
物品4	5kg
物品5	2kg

编写找出所有能将背包装满的解，如物品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]
"""

위 내용은 Python 알고리즘 응용 실무 스택의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!